עקרון שובך היונים
מתוך ויקיפדיה, האנציקלופדיה החופשית
.
עקרון שובך היונים, או בשמו השני: "עקרון דיריכלה", הוא עיקרון מתמטי הקובע כי אם יש m תאים בשובך שלתוכם יש להכניס m+1 יונים, קיים בהכרח תא אחד שבו תימצאנה לפחות שתי יונים. לעיקרון טריוויאלי זה יש שימושים רבים בהוכחות בתחום הקומבינטוריקה, וניתן להוכיח באמצעותו תוצאות רבות, מעניינות ובלתי טריוויאליות כלל.
תוכן עניינים |
[עריכה] הרחבת העיקרון
אם יש m תאים בשובך שלתוכם יש להכניס n יונים, אז בהכרח בתא אחד יהיו לפחות 
יונים או יותר, (p הוא המספר השלם הקרוב (בעיגול כלפי מעלה) למספר: n/m). כלומר יש תא שמספר היונים בו הוא לפחות כמו הממוצע.
הרחבה למקרה האינסופי: אם יש אינסוף יונים, ומספר סופי של תאים בשובך לתוכם יש להכניס את אינסוף היונים, בהכרח בתא אחד לפחות יהיו אינסוף יונים.
[עריכה] דוגמאות
דוגמאות נוספות ליישומים של העיקרון:
.
- בכל קבוצה בת שלושה עשר אנשים, יהיו לפחות שני אנשים שנולדו באותו חודש.
- יש במדינת ישראל לפחות שני אנשים עם אותו מספר שערות על ראשם; זאת מכיוון שמספר השערות האפשרי על ראשו של אדם מוערך בפחות ממיליון, ואילו מספר בני האדם בישראל הוא שבעה מיליון לערך (במקרה זה יש "תא שובך" לכל מספר שערות אפשרי, וה"יונים" הם תושבי ישראל).
- בכל קבוצה בת שלושה אנשים, יהיו בהכרח שני אנשים בני אותו מין. גרסה אחרת של אותה הבחנה, בצורת חידה, היא "כמה גרביים יש להוציא ממגירה המכילה גרביים שחורים ולבנים, בלא להביט, כדי להבטיח כי אפשר יהיה להרכיב זוג עם צבע אחיד".
דוגמה מתמטית אלמנטרית לשימוש בעקרון היא ההוכחה שבכל תת-קבוצה של 
ערכים מתוך הקבוצה 
יש שני ערכים כך שאחד מהם מחלק את השני. כדי לראות זאת, ניתן לכתוב כל מספר בקבוצה בצורה 
כש-
הוא אי זוגי וקטן מ-
( מתקבל פשוט על ידי חלוקה חוזרת ונשנית של המספר ב-2 עד שמתקבל ערך אי זוגי). יש רק n מספרים אי-זוגיים בין 1 ל-2n ולכן יש בקבוצה שני ערכים בעלי אותו חלק אי-זוגי m - ואחד מהם (זה שהחזקה של 2 עבורו היא קטנה יותר) בהכרח מחלק את השני.
[עריכה] הוכחת העיקרון
נניח כי לתוך m תאים בשובך יש להכניס n יונים. נכניס לכל תא יונה אחת לכל היותר. קיבלנו כי הכנסנו, במקרה המקסימלי, m יונים, בסתירה לכך ש: n > m.
עקב פשטות ההוכחה של הטענה נעשה בה שימוש רב במחקר העוסק בסיבוכיות של מערכות הוכחה (Proof Complexity).
[עריכה] ראו גם
[עריכה] לקריאה נוספת
- Martin Aigner, Günter M. Ziegler, Proofs from THE BOOK, Springer, 1998.
- Alexander Razborov, Proof Complexity of Pigeonhole Principles, Proceedings of the 5th DLT, Lecture Notes in Computer Science, vol. 2295, 2002, pages 100-116
