עקרון שובך היונים

שגיאה ביצירת תמונה ממוזערת:

ההשראה לעיקרון יונים בשובך. בתמונה זו n=10, m=9, ולכן על שתי יונים לפחות לחלוק תא אחד (m מייצג את מספר התאים בשובך ו-n את מספר היונים).

עקרון שובך היונים הוא עיקרון מתמטי הקובע כי אם יש $m$ תאים בשובך שלתוכם יש להכניס $m+1$ יונים, קיים בהכרח תא אחד שבו תימצא יותר מיונה אחת. עיקרון זה ככל הנראה נוסח לראשונה באופן פורמלי על ידי יוהאן דיריכלה בשנת 1834, ומכאן שמו הנוסף עקרון דיריכלה.

לעיקרון טריוויאלי זה יש שימושים רבים בהוכחות בקומבינטוריקה ומדעי המחשב, ועל אף פשטותו, ניתן להוכיח באמצעותו תוצאות רבות, מעניינות ובלתי טריוויאליות כלל.

הרחבת העיקרון

אם יש m תאים בשובך שלתוכם יש להכניס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} יונים, אז בהכרח בתא אחד יהיו לפחות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p= \lceil n/m \rceil} יונים או יותר, (הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle p } הוא המספר השלם הקרוב (בעיגול כלפי מעלה) למספר: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n/m} ). כלומר יש תא שמספר היונים בו הוא לפחות כמו הממוצע.

הרחבה למקרה האינסופי: אם יש אינסוף יונים, ומספר סופי של תאים בשובך לתוכם יש להכניס את אינסוף היונים, בהכרח בתא אחד לפחות יהיו אינסוף יונים.

הרחבה מקובלת נוספת: אם יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} תאים בשובך שלתוכם יש להכניס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m-1} יונים, אז בהכרח יישאר תא ריק אחד לפחות.

דוגמאות

שגיאה ביצירת תמונה ממוזערת:

עקרון שובך היונים מבטיח לנו שאם יש במגירה גרביים משני צבעים, כחולות וצהובות, אז מכל שלוש גרביים שנוציא מהמגירה, יהיו לפחות שני גרביים באותו צבע.

דוגמאות נוספות ליישומים של העיקרון:

• בכל קבוצה בת שלושה עשר אנשים יהיו לפחות שני אנשים שנולדו באותו חודש.
• יש במדינת ישראל לפחות שני אנשים עם אותו מספר שערות על ראשם; זאת מכיוון שמעריכים את מספר השערות האפשרי על ראשו של אדם בכמאה אלף, ואילו מספר התושבים במדינת ישראל הוא כמה מיליונים. בדוגמה זו ישנו תא שובך לכל מספר שערות אפשרי, והיונים הם תושבי מדינת ישראל.
• בכל תת-קבוצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n+1} ערכים מתוך הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left\{1,2,\dots,2n\right\}} יש שני ערכים כך שאחד מהם מחלק את השני. כדי לראות זאת, ניתן לכתוב כל מספר בקבוצה בצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2^k m} כש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ m} הוא אי זוגי וקטן מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2n} ($\ m$ מתקבל פשוט על ידי חלוקה חוזרת ונשנית של המספר ב-2 עד שמתקבל ערך אי זוגי). יש רק n מספרים אי-זוגיים בין 1 ל-2n ולכן יש בקבוצה שני ערכים בעלי אותו חלק אי-זוגי m - ואחד מהם (זה שהחזקה של 2 עבורו היא קטנה יותר) בהכרח מחלק את השני.
• דיריכלה עצמו השתמש בעיקרון כדי להוכיח כי כל מספר אי-רציונלי ניתן לקירוב דיופנטי מסדר שני (הוכחה).
• משפט ארדש-סקרש

הוכחת העיקרון

נניח בשלילה כי לתוך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} תאים בשובך יש להכניס n יונים. נכניס לכל תא יונה אחת לכל היותר. קיבלנו כי הכנסנו, במקרה המקסימלי, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} יונים, בסתירה לכך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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

קישורים חיצוניים

• עקרון שובך היונים, באתר MathWorld (באנגלית)
• "אבודים בריבוע, שובך יונים" ב"כאן חינוכית" (בעברית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

עקרון שובך היונים35928354Q188276