חידת מטוסים ומושבים

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

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

אתם האחרונים שנכנסים למטוס. מה ההסתברות שהכיסא שלכם פנוי?

תחשבו על זה קצת. התשובה לאחר הקומיקס.

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

אז מה כן עושים? ראשית כל, ברוב מוחץ של החידות מסוג זה, המספר 100 סתם בא להפחיד ואין לו חשיבות רבה. אם היה כתוב שם 200, הפתרון היה שונה? קרוב לודאי שלא. ואם היה כתוב 5? לכן כדאי תמיד להתחיל מלפתור מקרים פשוטים בצורה הכי ישירה שרק אפשר, וכך לקבל תחושת בטן כלשהי לגבי מה שהולך כאן. צריך להיזהר שהמקרים לא יהיו פשוטים מדי, כי במקרים כאלו קשה לראות את התבנית הכללית, אבל אין מניעה להתחיל אפילו מהם.

אם כן, כאשר יש רק נוסע אחד במטוס ההסתברות שלו להיות במקומו היא מן הסתם 1, אבל זו באמת סיטואציה מנוונת למדי כי כל עניין ה”איבדתי את הכרטיס” לא יכול לבוא בה לידי ביטוי מלכתחילה. אז בואו נתחיל מלהבין מה קורה כשיש שני נוסעים במטוס. במקרה הזה הנוסע השני - אתם - יתיישב במקומו רק אם הנוסע הראשון - המאבד - לא הגריל את המושב שלכם. מכיוון שיש שני מושבים בלבד, ההסתברות לכך היא \( \frac{1}{2} \).

כאשר יש שלושה אנשים העסק מתחיל להסתבך. הנוסע הראשון מגריל אחד משלושה מושבים. אם הוא הגריל את שלכם (בהסתברות \( \frac{1}{3} \)), אין סיכוי שתשבו במושב שלכם. אם הוא הגריל את המושב של עצמו (בהסתברות \( \frac{1}{3} \)) הכל בסדר - גם אתם וגם הנוסע הנוסף תשבו במושב הנכון שלכם. ואם הנוסע הראשון הגריל את המושב של הנוסע השני? אז הכל תלוי במה שהנוסע השני יעשה, והוא בוחר בין שני מושבים אפשריים, כך שבהסתברות \( \frac{1}{2} \) הוא יבחר במושב ה”נכון” (זה שאינו שלנו, כלומר זה שנוסע מס’ 1 היה אמור לשבת בו), וקיבלנו שבסך הכל ההסתברות לכך שהמושב שלנו יהיה פנוי היא \( \frac{1}{3}+\frac{1}{3}\cdot\frac{1}{2}=\frac{1}{2} \).

הממממ.

קיבלנו שוב חצי.

האם אני מריח הכללה מתקרבת ובאה?

בשלב הזה גם התעוררו החשדות שלי, אבל גם התחלתי לראות דרך כללית לפתור את הבעיה. בואו נסמן את הנוסעים במספרים, \( 1,2,\dots,n \) ואת המושבים שלהם נסמן באותם מספרים. כעת, אפשר לחלק את ההתרחשות במטוס למקרים על פי השאלה איפה נוסע 1 התיישב. אם הוא התיישב בכיסא 1 (בהסתברות \( \frac{1}{n} \)) אז כל שאר הנוסעים גם כן ישבו במקומותיהם וההסתברות שלנו (נוסע \( n \)) לשבת במקומנו היא 1. אם נוסע 1 התיישב בכיסא 2, אז נוסע 2 בוחר מושב באקראי מבין \( n-1 \) המושבים שנותרו; אפשר לחשוב על כך כאילו מושב 1 הוא המושב ה”נכון” עבורו, ולכן הסיטואציה זהה לזו של החידה המקורית, אבל עם אדם אחד פחות. אם נסמן ב-\( B\left(n\right) \) את ההסתברות כאשר יש \( n \) אנשים, אז ראינו בינתיים ש-\( B\left(n\right)=\frac{1}{n}+\frac{1}{n}B\left(n-1\right)+\dots \) כשאני עדיין לא יודע מה מסתתר מאחורי שלוש הנקודות, אבל אפשר כבר לנחש.

אם נוסע 1 התיישב במושב 3, אז נפטרנו משני אנשים: גם מנוסע מס’ 1 אבל גם מנוסע מס’ 2 שיתיישב במושב 2 וחסל. זה אומר שהמשחק מתחיל מחדש עם נוסע 3, ולכן צריך להוסיף לסכום שלנו גם \( \frac{1}{n}B\left(n-2\right) \). ואותו דבר עם נוסע מס’ 4, וכו’ וכו’ וכו’. זאת עד לסיטואציה שבה נוסע מס’ 1 מתיישב במקום \( n \) - המקום שלנו! - ואז אין לנו שום סיכוי לשבת יותר במקום שלנו ולכן זה לא נכלל בסכום.

קיבלנו את הנוסחה \( B\left(n\right)=\frac{1+B\left(n-1\right)+B\left(n-2\right)+\dots+B\left(2\right)}{n} \) (ואם רוצים נוסחה יפה עוד יותר אפשר להסכים ש-\( B\left(0\right)=0 \) ו-\( B\left(1\right)=1 \) ולכתוב \( B\left(n\right)=\frac{1}{n}\sum_{k=0}^{n-1}B\left(k\right) \)). כעת, אם נלך עם תחושת הבטן שלנו וננסה להוכיח ש-\( B\left(n\right)=\frac{1}{2} \) לכל \( n\ge2 \) (עבור 2 כבר ראינו שזה קורה), מה הנוסחה תיתן לנו? ובכן:

\( B\left(n\right)=\frac{1+\frac{1}{2}+\dots+\frac{1}{2}}{n}=\frac{1}{n}\left(1+\frac{n-2}{2}\right)=\frac{1}{n}\cdot\frac{n}{2}=\frac{1}{2} \)

(מאיפה ה-\( \frac{n-2}{2} \) הגיע? יש בדיוק \( n-2 \) מחוברים שהערך שלהם, על פי הנחת האינדוקציה, הוא \( \frac{1}{2} \): המחוברים \( B\left(2\right),\dots,B\left(n-1\right) \)).

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

האבחנה הבסיסית היא זו: אם נתבונן באחד מהתרחישים האפשריים של “איך אנשים תופסים מקומות במטוס”, נשים לב לכך שהשאלה האם כשאתם (הנוסע האחרון) תיכנסו מושב 100 יהיה פנוי שקולה לשאלה האם מושב 100 נתפס לפני מושב 1. למה? טוב, אם מושב 100 נתפס לפני מושב 1, אז בפרט כשאתם נכנסים למטוס לא ייתכן שמושב 100 עדיין פנוי (כי יש רק מושב פנוי יחיד, ומבין המושבים 1 ו-100, מושב 1 נתפס מאוחר יותר ולכן אם מישהו משניהם פנוי זה יהיה מושב 1). מצד שני, אם מושב 1 נתפס לפני מושב 100, “הכל מסתדר”. תחשבו על זה שניה: בכל פעם שבה אדם מתיישב במושב שאינו שלו, הכל מסתדר עד לרגע שבו בעליו החוקיים של המושב נכנס למטוס; עד שזה קורה, כל אלו שנכנסים למטוס נכסים למקומות החוקיים שלהם. זה רק הבעלים של המושב החוקי שנתפס שנאלץ להגריל מושב של מישהו אחר. אבל, אם יוגרל מושב מס’ 1, אף אחד כבר לא יסבול מכך שתפסו לו את המקום שכן מושב 1 היה שייך למופרע שהתחיל את כל המהומה הזו. מכאן שאם לא תפסו את מושב 100 עד אשר תפסו את מושב 1, גם לא יתפסו בטעות את מושב 100 החל מאותו רגע.

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

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

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