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

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

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

ההוכחה מתבססת על עיקרון שנקרא “עקרון שובך היונים”: אם \(101\) יונים (או יותר) תיכנסנה ל-\(100\) תאים, יהיה תא שאליו ייכנסו לפחות שתי יונים. באופן כללי, אם מספר היונים גדול ממספר התאים, תצטרכנה שתי יונים (לפחות) להצטופף בתא אחד. הניסוח הכללי של המשפט הוא: כשמחלקים יותר מ-\(n\) עצמים ל-\(n\) סוגים (“תאים”), יהיו לפחות שניים מאותו סוג.

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

בואו נחזור עתה לשערם של תושבי תל אביב. עובדה היא שלאדם יש לכל היותר \(100,000\) שערות על ראשו. בתל אביב יש (נאמר) \(300,000\) אנשים, ואם מתעקשים על הנוסח של בני האדם הלא קירחים, מותר להניח שלפחות \(200,000\) מתוכם אינם קירחים. אם נחלק את תושבי תל אביב הלא קירחים לסוגים על פי מספר שערותיהם (כלומר בסוג הראשון אלה שיש להם שערה אחת על ראשם, בסוג השני אלה שיש להם \(2\) שערות על ראשם, וכו’), יתברר שיש יותר אנשים מאשר סוגים. לכן יהיו שני אנשים מאותו “סוג”, כלומר שני אנשים עם אותו מספר שערות.

קבוצות עצמאיות

קבוצת מספרים שלמים נקראת “עצמאית” (זהו שם שהמצאתי לצורך העניין) אם אין בה מספר אחד שמתחלק במספר אחר. למשל, הקבוצה \({3,5,6}\) אינה עצמאית, משום ש-\(6\) מתחלק ב-\(3\). הקבוצה \({3,4,5}\) היא עצמאית, משום ש-\(5\) אינו מתחלק ב-\(4\) או ב-\(3\), ו-\(4\) אינו מתחלק ב-\(3\).

כמה גדולה יכולה להיות קבוצה עצמאית של מספרים בין \(1\) ל-\(100\)?

כזכור, כלל יסוד בפתרון בעיות הוא לפתוח בדוגמאות פשוטות. במקרה זה כדאי להחליף תחילה את המספר \(100\) במספרים קטנים יותר, כאשר מותר, ואף רצוי, לקחת את הדבר לקיצוניות, כלומר לקחת מספרים קטנים ככל האפשר. נשאל אפוא תחילה מהו הגודל המקסימלי של קבוצה עצמאית של מספרים בין \(1\) ל-\(1\). כמובן: הקבוצה \({1}\) היא קבוצה עצמאית, ולכן הקבוצה העצמאית המקסימלית מכילה איבר אחד. ומה באשר למספרים בין \(1\) ל-\(2\)? הקבוצה \({1,2}\) אינה עצמאית (\(1\) מחלק את \(2\)), ולפיכך אפשר רק לקחת או את \({1}\), או את \({2}\) – גם במקרה זה הגודל המקסימלי של קבוצה עצמאית הוא \(1\). בין \(1\) ל-\(3\)? הקבוצה \({2,3}\) היא עצמאית, ומכילה שני איברים. בין \(1\) ל-\(4\): הקבוצה \({3,4}\) עצמאית, וכן \({2,3}\), וקל לראות שאין קבוצה עצמאית בת \(3\) איברים, אם כך גם במקרה זה התשובה היא \(2\). בואו נדלג עתה ל-\(10\): הקבוצה \({6,7,8,9,10}\) עצמאית, וכן הקבוצות  \({5,6,7,8,9}\) ו-\({4,5,6,7,9}\). בכל אלה יש \(5\) איברים. קל למדי לבדוק שאין קבוצה עצמאית בגודל \(6\).

מן הדוגמאות שהובאו אפשר לנחש שאם \(n\) הוא מספר זוגי אז הגודל המקסימלי של קבוצה עצמאית של מספרים בין \(1\) ובין \(n\) הוא חצי מ-\(n\). אם \(n\) אי זוגי, כי אז הגודל המקסימלי הוא חצי מ-\(n+1\). למשל, קל למצוא קבוצה עצמאית בגודל \(50\) של מספרים בין \(1\) ו-\(100\): \({51,52,53,…,99,100}\), או גם \({49,50,51,52,…,99}\). אבל איך להוכיח שאין קבוצה עצמאית בת יותר מ-\(50\) איברים? הנה דרך יפה לכך. אנו רוצים להוכיח שקבוצה בת \(51\) איברים בהכרח אינה עצמאית. כלומר:

בקבוצה בת \(51\) מספרים בין \(1\) ל-\(100\) יש בהכרח שני מספרים שהאחד מהם מתחלק באחר.

ההוכחה נעזרת בעקרון שובך היונים. כרגיל, אקורד הסיום של ההוכחה, שהוא השימוש בעיקרון, לא יהיה קשה. הקושי הוא בשלב הראשון, של הגדרת תאי השובך. בין \(1\) ל-\(100\) יש \(50\) מספרים אי זוגיים. לכל מספר אי זוגי נגדיר “תא”, שהוא קבוצה של מספרים. תא זה יכיל את כפולות המספר האי זוגי האמור בחזקות של \(2\), כלומר במספרים\(1,2,4,8,16,…\). למשל, התא המתאים למספר האי זוגי \(3\) יכיל את המספרים: \(3*1=3\) , וכן את \(3*2=6\), את \(3*4=12\), את \(3*8=24\), ואת \(3*32=96\) (אנו לוקחים רק את הכפולות שאינן עוברות את \(100\), משום שאנו מחלקים רק את המספרים בין \(1\) ו-\(100\) לתאים). התא המתאים למספר האי זוגי \(25\) מכיל את \(25\), \(50\) ו-\(100\). התא המתאים ל-\(49\) מכיל רק שני מספרים – \(49\) עצמו, ו-\(98\) (הכפולה הבאה, ב-\(4\), כבר חורגת מן התחום). החל מן התא המתאים ל-\(51\), כל תא מכיל רק מספר אחד. התאים יהיו אפוא אלה:

\(1,2,4,8,16,32,64\) (אלה הן כפולות \(1\) בחזקות של \(2\));

\(3,6,12,24,48,96\) (כפולות \(3\) בחזקות של \(2\));

\(5,10,20,40,80\) (כפולות \(5\) בחזקות של \(2\));

\(7,14,28,56\) (כפולות \(7\) בחזקות של \(2\));

\(\dots\) (אני מדלג כאן על כפולות \(9,11,13,\dots\))

\(49,98\) (כפולות \(49\) בחזקות של \(2\));

\(51\)

\(53\)

\(\dots\)

\(99\)

נשים עתה לב לכך שכל מספר בין \(1\) ל-\(100\) מופיע באחד התאים. אראה זאת בדוגמה. באיזה תא יופיע למשל \(92\) ? חלקו את \(92\)  ב-\(2\), ותקבלו \(46\); חלקו את \(46\) ב-\(2\), ותקבלו \(23\), שהוא מספר אי זוגי. אם כך \(92-23*2^2\), ולכן \(92\) יופיע בתא ה-\(23\), המכיל את כפולות \(23\) בחזקות של \(2\). אפשר לעשות כך עם כל מספר – למצות ממנו את חזקות \(2\) על ידי חלוקה נשנית ב-\(2\), עד שמגיעים למספר אי זוגי. הנה כי כן המספרים בין \(1\) ל-\(100\) מתחלקים ל-\(50\) תאים. על פי עקרון שובך היונים, אם ניקח קבוצה בת \(51\) מספרים יהיו בה שני מספרים שישתייכו לאותו תא. אבל שימו לב: אם שני מספרים שייכים לאותו תא, הגדול מהם מתחלק בקטן. למשל, המספרים \(12\) ו-\(96\) שייכים שניהם לתא של \(3\), משום ש:\(3*4=12\)   ו-\(3*32=96\) . ואכן \(96\) מתחלק ב-\(12\) (משום ש-\(4\) מחלק את \(32\)). מכיוון שהראינו שבין \(51\) מספרים יש שניים שנמצאים באותו תא, הוכחנו לפיכך שבקבוצה של \(51\) מספרים בין \(1\) ל-\(100\) חייבים להיות שניים שהאחד מתחלק בחברו.

מספרים זרים

למתמטיקאי ההונגרי הגדול אֶרְדֶש סופַּר על ילד פלא, לָיוֹש פּושָה (Lajos Posa), שבגיל \(12\) כבר ידע מתמטיקה גבוהה. ארדש הזמין את פּושָה הצעיר למסעדה ואיתגר אותו: “הוכח לי שבקבוצה של \(51\) מספרים בין \(1\) ל-\(100\) יש שני מספרים זרים”, שפירושו מספרים שאין להם גורם משותף (כלומר שאין מספר, פרט ל-\(1\), המחלק את שניהם). פּושָה הרים את ראשו מקערת המרק ואמר: “בקבוצה של \(51\) מספרים בין \(1\) ל-\(100\) יש שני מספרים עוקבים” (כלומר נבדלים ב-\(1\)). כמובן, שני מספרים עוקבים הם זרים – אם למשל מספר מתחלק ב-\(3\), העוקב לו אינו מתחלק ב-\(3\).

גם כאן חבוי למעשה עקרון שובך היונים. הדרך הפשוטה ביותר להוכיח שבין \(51\) מספרים בין \(1\) ל-\(100\) יש שניים עוקבים היא לחלק את המספרים ל-\(50\) “תאים” של זוגות עוקבים: \({1,2},{3,4},{5,6},\dots,{99,100}\). בין \(51\) המספרים בקבוצה הנתונה יהיו שניים השייכים לאותו “תא”, שפירושו שהם יהיו עוקבים.

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

3 תגובות על עקרון שובך היונים

  • מאת עמי סגל‏:

    האם נכון לומר שהקבוצה השנייה הרשומה מ-49 עד 99 בת 51 איברים ומתקיים בה 49*2=98 ועל כן אינה עצמאית.

  • מאת יוסי כהן‏:

    עמי שלום,

    בשל תקלה שקרתה לא הועברה העובדה שהגבת. בקרוב תקבל תשובה. סליחה…

  • מאת רון‏:

    צודק לגמרי, תודה על הערנות. אני משער שהכוונה הייתה ל:
    49, 50, 51, …, 97, 99