צילום: Alexandre Chambon, Unsplash דרך Wikimedia Commons (CC0)

הנה טענה שנשמעת כמו ניחוש פרוע:

בתל אביב-יפו חיים לפחות שני אנשים שיש להם בדיוק אותו מספר שערות על הראש.

לא "בערך אותו מספר". בדיוק אותו מספר, שערה בשערה.

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

שני נתונים בלבד דרושים לכם:

בתל אביב-יפו חיים כ-480,000 תושבים.
מספר השערות על ראשו של אדם נע בדרך כלל בין 100,000 ל-150,000, ובוודאות אינו עולה על 250,000.

השאלה: איך מוכיחים את הטענה בלי לספור אף שערה אחת?

רמז דק

תפסיקו לחשוב על שערות. תחשבו על מגירות.

כמה ערכים שונים בכלל יכולים להיות ל"מספר השערות על הראש"? וכמה אנשים צריך לחלק בין הערכים האלה?

רמז עבה

דמיינו שורה ארוכה של מגירות, ממוספרות מ-0 ועד 250,000. זהו סך הכול 250,001 מגירות.

עכשיו קחו כל תושב והכניסו אותו למגירה שמספרה שווה למספר השערות שלו.

מה חייב לקרות כשמכניסים 480,000 אנשים ל-250,001 מגירות?

פתרון

ההוכחה

לכל תושב יש מספר שערות שהוא מספר שלם בין 0 ל-250,000. כלומר יש 250,001 ערכים אפשריים בלבד.

מספר התושבים הוא כ-480,000 - יותר מפי אחת וחצי ממספר הערכים האפשריים.

אם כל תושב היה בעל מספר שערות שונה מכל האחרים, היינו זקוקים ל-480,000 ערכים שונים לפחות. אבל קיימים רק 250,001. לכן זה בלתי אפשרי, וחייבים להימצא לפחות שניים בעלי אותו מספר בדיוק.

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

אפשר אפילו לומר יותר

אם נשתמש בטווח המציאותי יותר - עד 150,000 שערות, כלומר 150,001 ערכים אפשריים - נקבל ש-480,000 חלקי 150,001 גדול מ-3. כלומר קיימת קבוצה של לפחות ארבעה תושבים בעלי מספר שערות זהה לחלוטין.

מי היה דיריכלה

העיקרון הזה נקרא עקרון שובך היונים, ובגרמנית "Schubfachprinzip" - עקרון המגירות. הוא נוסח באופן מפורש בשנת 1834 על ידי המתמטיקאי הגרמני פטר גוסטב לז'ן דיריכלה.

הניסוח הכללי פשוט להפליא: אם מחלקים n פריטים ל-m קבוצות ומתקיים n גדול מ-m, אז קיימת קבוצה אחת לפחות שיש בה שני פריטים או יותר.

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

עוד שימושים מפתיעים

בכל קבוצה של 13 אנשים, יש שניים לפחות שנולדו באותו חודש.
בכל קבוצה של 367 אנשים, יש שניים לפחות שנולדו באותו יום בשנה.
אם מניחים 5 נקודות בתוך ריבוע שצלעו 1, תמיד יימצאו שתי נקודות שהמרחק ביניהן קטן מ-0.75.

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