הצגת המקור של הדף "עקרון שובך היונים"

[[קובץ:TooManyPigeons.jpg|שמאל|ממוזער|250px|מקובל להדגים עיקרון זה באמצעות יונים ב[[שובך]]. כאשר 10 יונים נמצאות ב-9 תאים בשובך, תא אחד לפחות חייב להכיל לפחות שתי יונים.]]
'''עֶקרון שובך היונים''' או '''עֶקרון דיריכלה''' הוא עיקרון [[מתמטיקה|מתמטי]] הקובע כי אם <math>n</math> פריטים מפוזרים בין <math>n-1</math> תאים, אז בהכרח ישנו תא אחד לפחות המכיל יותר מפריט אחד. באופן כללי יותר, כלל זה קובע כי לכל <math>n</math> פריטים המפוזרים בין <math>m</math> תאים כך ש<math>n>m</math>, אז בהכרח בלפחות תא אחד יימצאו לפחות <math>\lceil n/m \rceil</math> פריטים, כלומר קיים תא שמספר הפריטים בו הוא לפחות כמו הממוצע.

עיקרון זה נוסח ככל הנראה לראשונה בצורה רשמית בשנת 1834 בידי ה[[מתמטיקאי]] ה[[גרמני]] [[יוהאן פטר גוסטב לז'ן דיריכלה|יוהאן דיריכלה]].

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

==הרחבת העיקרון==
הרחבה למקרה ה[[אינסוף|אינסופי]]: אם יש אינסוף יונים, ומספר סופי של תאים בשובך לתוכם יש להכניס את אינסוף היונים, בהכרח בתא אחד לפחות יהיו אינסוף יונים.

הרחבה מקובלת נוספת: אם יש <math>m</math> תאים בשובך שלתוכם יש להכניס <math>m-1</math> יונים, אז בהכרח יישאר תא ריק אחד לפחות.

==דוגמאות==
[[קובץ:Socken_farbig.jpeg|ממוזער|200px|עקרון שובך היונים מבטיח לנו שאם יש במגירה גרביים משני צבעים,  כחולות וצהובות, אז מכל שלוש גרביים שנוציא מהמגירה, יהיו לפחות שתי גרביים באותו צבע.]]
דוגמאות נוספות ליישומים של העיקרון:
*בכל קבוצה בת שלושה עשר אנשים יהיו לפחות שני אנשים שנולדו באותו [[חודש]].
*יש במדינת [[ישראל]] לפחות שני אנשים עם אותו מספר [[שערות]] על ראשם; זאת מכיוון שמעריכים את מספר השערות האפשרי על ראשו של אדם בכמאה אלף, ואילו מספר התושבים במדינת ישראל הוא כמה מיליונים. בדוגמה זו ישנו תא שובך לכל מספר שערות אפשרי, והיונים הם תושבי מדינת ישראל.
*בכל תת-קבוצה של <math>\ n+1</math> ערכים מתוך הקבוצה <math>\ \left\{1,2,\dots,2n\right\}</math> יש שני ערכים כך שאחד מהם מחלק את השני. כדי לראות זאת, ניתן לכתוב כל מספר בקבוצה בצורה <math>\ 2^k m</math> כש-<math>\ m</math> הוא אי זוגי וקטן מ-<math>\ 2n</math> (<math>\ m</math> מתקבל פשוט על ידי חלוקה חוזרת ונשנית של המספר ב-2 עד שמתקבל ערך אי זוגי). יש רק n מספרים אי-זוגיים בין 1 ל-2n ולכן יש בקבוצה שני ערכים בעלי אותו חלק אי-זוגי m - ואחד מהם (זה שהחזקה של 2 עבורו היא קטנה יותר) בהכרח מחלק את השני.
*[[יוהאן פטר גוסטב לז'ן דיריכלה|דיריכלה]] עצמו השתמש בעיקרון כדי להוכיח כי כל [[מספר אי-רציונלי]] ניתן ל[[קירוב דיופנטי]] מסדר שני ([[קירוב דיופנטי#קירוב דיופנטי של מספר ממשי|הוכחה]]).
* [[משפט ארדש-סקרש]].

==הוכחת העיקרון==
[[הוכחה בדרך השלילה|נניח בשלילה]] כי חולקו <math>n</math> פריטים בין <math>m</math>תאים ושבכל התאים ישנם לכל היותר <math>\lceil n/m \rceil-1</math> פריטים. בעקבות הנחה זו, מספר הפריטים הכולל בתאים הוא לכל היותר <math>m(\lceil n/m \rceil-1)</math>. סכום זה קטן מ-<math>n</math> ולכן נגיע ל[[סתירה (לוגיקה)|סתירה]].

עקב פשטותה של ההוכחה נעשה בה שימוש רב במחקר העוסק ב[[סיבוכיות]] של מערכות הוכחה (Proof Complexity).

== ראו גם ==
* [[המלון של הילברט]]
* [[פרדוקס יום ההולדת]]

==לקריאה נוספת==
<div style="direction: ltr;">
*Martin Aigner, Günter M. Ziegler, '''Proofs from THE BOOK''', Springer, 1998.
*Alexander Razborov, [http://www.mi.ras.ru/~razborov/php_survey.ps Proof Complexity of Pigeonhole Principles], Proceedings of the 5th DLT, Lecture Notes in Computer Science, vol. 2295, 2002, pages 100-116
</div>

==קישורים חיצוניים==
* {{MathWorld}}
* "[[אבודים בריבוע]], [https://www.youtube.com/watch?v=dcm_aRAOxqc שובך יונים" ב"כאן חינוכית"] (בעברית)

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:משפטים בקומבינטוריקה]]
[[קטגוריה:שיטות הוכחה]]