חידת קופסאות

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

מן הסתם שורש העניין נעוץ באיזו שיטת פעולה שעליה אליס ובוב הסכימו מראש – השיטה שעל פיה אליס החליטה אם ואיך להחליף את הפתקים היא משהו שהיא הסכימה עליו מראש עם בוב. עם זאת, מרגע שהמשחק התחיל אין ביניהם שום תקשורת – אליס לא יכולה לומר לבוב מה נמצא באיזו קופסה, ובוב בוודאי לא יכול להגיד לאליס איזה מספר יבקשו ממנו למצוא כי הוא עוד לא יודע את זה בזמן שאליס נכנסת לחדר (ולמעשה, חבר השופטים יכול לראות איזו החלפה אליס ביצעה ולבחור בכוונה מספר "גרוע" אם מתחשק לו).

אם כן, השאלה היא – מה תהיה שיטת הפעולה של אליס ובוב בעניין?

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


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

שיטת חיפוש אחת שבוב יכול לנקוט בה הוא פשוט לפתוח קופסאות באופן אקראי. טוב, זה לא יוביל לכלום מן הסתם. הוא גם יכול לפתוח קופסאות באופן סדרתי – 1,2,3 וכן הלאה. גם זה, די בבירור, לא יוביל לכלום. השיטה הבאה בתור נראתה לי טבעית ביותר, אם כי אולי לא תסכימו איתי. הרעיון הוא לטייל בתוך המעגלים הזרים שמרכיבים את התמורה. מה זה אומר בפועל? פשוט מאוד. נניח שאומרים לבוב לחפש את המספר 2. הוא יפתח את קופסה מס' 2. אם 2 שם, יופי. אחרת יש שם מספר אחר, נניח 33. כעת בוב יפתח את קופסה 33. אם 2 שם, יופי. אחרת יש שם מספר אחר – נניח, 13. אז בוב יפתח את קופסה 13… הבנתם את העיקרון.

נוצר לנו מסלול שאפשר לתאר בערך כך: $latex 2\to33\to13\to\dots$. מתי מסלול כזה יכול להסתיים? רק כשבוב מגיע למספר של קופסה שכבר הופיע בעבר. אני טוען שהמספר הזה חייב להיות 2. למה? ובכן, נניח שזה מספר אחר, נניח 33. אז זה אומר שבוב פתח קופסה שבה היה כתוב המספר 33 – אבל הוא כבר עשה את זה קודם, בהתחלה, כשפתח את קופסה מספר 2! ומכיוון ש-33 לא מופיע פעמיים בקופסאות, לא ייתכן שבוב נתקל בו שוב לפני שנתקל ב-2. לכן בוב מגיע בסופו של דבר ל-2, אבל השאלה היא – כמה מהר?

לרוע המזל, ייתכן שהוא מגיע לשם לאט מאוד – ייתכן שהוא עובר על פני כל שאר הקופסאות עד שהוא מגיע ל-2. אלא שכאן אליס נחלצת לעזרתו. אליס פותחת את כל הקופסאות ולכן יודעת בדיוק מהם כל המעגלים שמרכיבים את התמורה. אם יש מעגל ארוך – שאורכו גדול מ-50 – אז אליס תבצע החלפה כדי לפצל אותו ל-2. אחרת, אליס לא תעשה כלום. בכל מקרה אחרי שאליס מסיימת כל המעגלים שמרכיבים את התמורה הם מגודל לכל היותר 50, ולכן טיול כמו שבוב מבצע בהם יסתיים תוך 50 בדיקות לכל היותר, וחסל. אם כן, מה שבוב עושה הוא פשוט: אם אמרו לו לחפש את המספר ה-$latex k$, הוא פשוט פותח את הקופסה ה-$latex k$-ית ומשם הוא ממשיך על פי המספר שהוא מצא בתוך הקופסה שפתח. המעגל יסתיים בדיוק כשבוב ימצא את המספר המבוקש.

נשאר רק להסביר איך אליס מבצעת את הפיצול, אבל זה פשוט. נניח שיש לנו מעגל $latex 1\to2\to3\to\dots\to n\to n+1\to\dots\to2n\to1$ (המספרים מסודרים בסדר עולה לצורך פשטות). אז אורך המעגל הוא $latex 2n$ ואנו רוצים לפצל אותו ל-2 מעגלים שונים מאורך $latex n$ כל אחד. כרגע הסיטואציה היא כזו שבקופסה מס' $latex 2n$ יש את הפתק $latex 1$, ובקופסה מס' $latex n$ יש את הפתק $latex n+1$. אליס פשוט תחליף את שני הפתקים הללו. התוצאה? המעגל $latex 1\to2\to3\to\dots\to n\to1$ (כי בקופסה $latex n$ נמצא כעת המספר 1) והמעגל $latex n+1\to\dots\to2n\to n+1$ (כי בקופסה מס' $latex 2n$ נמצא כעת הפתק $latex n+1$). באופן הזה אליס מסוגלת לפצל כל מעגל גדול לשני מעגלים קטנים יחסית, וזה כבר באמת סוף הפתרון.

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

41 תגובות בנושא “חידת קופסאות”

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

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

  3. חידה מאוד מעניינת!
    גאווה כלשהי לשמוע שכיוון המחשבה (השגוי) הראשון שלי היה כמו שלך…

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

  5. שלום גדי,

    כתבת בחידה שיש חדר עם 100 קופסאות ולא ציינת שהן מסודרות בסדר כלשהוא.
    בלי הפרט הזה אין כל כך משמעות ל: "קופסה מספר 2" או כל מספר אחר..

    בלי קשר, תודה על הבלוג, אני ממש מבסוט עליו.

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

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

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

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

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

  11. יש חידה דומה שמופיעה במאמר של ANDY YAO אם אני זוכר נגון. (זה קשור למשהו בסיבוכיות, שוב אני לא זוכר ומתעצל לחפש). החידה היא:מאה המספרים 1 עד 100 מסודרים במאה קופסאות בסדר *אקראי*. מאש אנשים, שגם הם ממוספרים 1 עד 100 נשלחים לחדר, כל אחד רוצה למצוא את המספר "שלו", ומותר לו לפתוח רק 50 קופסאות, ואסור לו להזיז כלום. תנו אסטרטגיה שתבטיח שההסתברות *שכולם* מצליחים היא לפחות 1 חלקי 20.

    (שימו לב: כל אחד בנפרד יצליח לכל היותר בהסתברות חצי, אבל מאה המאורעות אינם בלתי תלויים).

    למתקדמים מה האסטרטגיה שתמקסם את הסיכוי שכולם מצליחים?

  12. האם שמה של אליס הוא על שם אליס מהארץ, אם כך אנלוגיה יפה ומחווה ללואיס קרול!

    לפוסט הנוכחי, אכן חידה מרתקת.

    1. כנראה שלא. אליס ובוב הם שמות מקובלים ל"שחקנים" בסיטואציות שדורשות שני שחקנים, בגלל שהשמות שלהם מתחילים ב-A ו-B.

      כמובן, אולי השם אליס נבחר לראשונה בגלל אליס של קארול, אבל אני לא יודע.

  13. [שחקן שלישי מכונה צ'ארלי, אלא כן אליס ובוב "משחקים נגדו" ואז הוא מכונה אוסקר (כנראה כי Oscar ו Opponent מתחילים שניהם ב O, מה שנפוץ מאוד בסיטואציות של הצפנה- אליס מעבירה לבוב מסר מוצפן ואוסקר מנסה לפענח אותו
    ואגב, לואיס קרול זה לא ההוא שרץ ממש מהר בשנות השמונים ובסוף הפסיד לבן ג'ונסון?].

  14. תשובה לאלעד-II, האסטרטגיה היא למספר את הקופסאות (מבחוץ) וכל איש מתחיל בקופסא מהמספר שלו
    ומשם ממשיך הלאה לפי המספר שמצא בתוך הקופסא (בדומה ל בוב). למעשה הבעיה עוברת לבעיה מסוג אחר והשאלה שנשאלת היא מה ההסתברות לקיום מעגל מקסימלי קטן או שווה ל 50 (מקסמיום צעדים מותרים). מסתבר שהתשובה היא באיזור ה- 30% זה נראה קצת כמו קסם. אני לא יודע אם יש זו סתם הסתברות או שיש כאן משהו מעבר. מישהוא יודע?

  15. [דן, חידה הרבה יותר גדולה זה איך למען השם הגעת לפורום סמי?? זה אמיתי הדבר הזה?]
    גדי, חידה באמת נהדרת. היה נחמד אם היית מוסיף שהתמורה מורכבת מאוסף מעגלים זרים (הבנתי את זה אמנם, אבל לקח לי כמה דקות)

  16. גם אני נפלתי במלכודת של לנסות להעביר מידע באמצעות הקופסה הראשונה. עוד בלבל אותי שזה דווקא אפשרי במקרה של 4 קופסאות. בוב יסתכל על הקופסה הראשונה ויסיק את המיקום של 3 האחרות. הוא יכיר את התמורות:
    1234
    2341
    3412
    4123
    ניתן להראות שאפשר לעבור באמצעות החלפה אחת לכל היותר מכל תמורה אחרת לאחת מהתמורות האלה.
    הבעיה שהשיטה הזאת נופלת מבחינה קומבינטורית כבר עם 6 קופסאות. אבל לכמה זמן חשבתי שאם זה עובד ל2 ול4 אז באינודקציה זה נכון לכל n 🙂

  17. הכוונה כמובן שבוב היה מסתכל ב-n-1 הקופסאות הראשונות ולפיהן היה מסיק על המיקומים בשאר הקופסאות אם יש לו n נסיונות

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

  19. גדי, כתבת שאם המעגל הארוך ביותר הוא פחות מ-50 אליס לא תבצע פיצול.
    האם ביצוע פיצול במעגל הארוך ביותר שנמצא היא לא טקטיקה עדיפה למציאת המספר בצורה מהירה יותר? אבהיר – אם נתון מעגל שמורכב מ-40 מספרים ומתוך אחד ממספריו בוב מתבקש למצוא מספר כלשהו – אם נבצע פיצול ל-20 ו-20 בוב ימצא את המספר המבוקש בתוך 20 ניסיונות במקום 40 בכל מקרה.
    תודה, אחלה חידה!

  20. נראה לי שאתה צודק, אבל מכיוון שאליס ובוב הם בדיוניים ולא באמת יפתחו קופסאות לא ראיתי צורך לאפטמז את התוצאה, ואני מעדיף בסיטואציות כאלו להציג פתרון "נקי" יחסית (כמובן שאפשר לטעון שדווקא הפתרון של "לפצל תמיד" שלא כולל חלוקה למקרים הוא נקי יותר; עניין של נקודת מבט לדעתי).

  21. היי גדי.

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

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

    יישר כוח!

    נ.ב.

    האם האתר עדיין מתעדכן בפוסטים חדשים?

  22. סתם לידע : אילו אליס לא היתה במשחק, אז נשאלת השאלה מה הסיכוי שהמעגל המקסימלי קטן שווה ל50 על מנת שבוב יצליח במשימה.
    נחשב את הסיכוי למעגל באורך K (גדול או שווה ל51)
    (100 בחר K) – בחירת K האיברים שהשתתפו במעגל הנל
    (k-1)! – סידור K האנשים (שיועדו להשתתף במעגל) כך שיהיה מעגל באורך K (הראשון יכול לבחור את כולם מלבד עצמו – כדי לא לסגור מעגל וכן הלאה
    (100 פחות K)! – סידור שאר האנשים שאינם במעגל בסדר אקראי
    –> סיכוי למעגל באורך k = מכפלת כל הגורמים מקודם, חלקי סה"כ האפשרויות (100!)
    –> ומקבלים כי הסיכוי למעגל באורך k הוא 1/k (שוב – מעגל באורך גדול מ50) לכן הסיכוי למעגל באורך 51 עד 100 הוא – סכום של 1/k, k רץ מ51 עד 100 שזה שווה בקירוב לאינטגרל של 1/k מ50 עד 100 = ln100-ln50 = ln2=0.7 לכן המאורע המשלים שהוא – מעגל מקסימלי באורך 50 מתקבל בסיכוי 0.3, שזה הסיכוי שבוב יצליח משימה ללא אליס (בקירוב כמובן / ניתן להעריך את ההפרש בין הטור ההרמוני לפונקציית ה ln – במקרה הזה ההפרש זניח)

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

    תודה מראש על התשובה, הבלוג שלך באמת מרתק!

  24. העניין הוא בכך שלא יכולים להיות *שני* מעגלים שארוכים יותר מ-50, כי אז בהכרח יהיה איבר שמשותף לשניהם. תחשוב רגע ותראה שאם יש איבר שמשותף לשני המעגלים, אז הם זהים.

  25. שאלה לגדי בקשר למה שמורן נחושתן כתב (הוא התעלם ממצב בו קיים מעגל גדול מ-50 ולמרות זאת בוב לא יכנס אליו בניסיון שלו)…

    אני מקבל את העובדה שההסתברות שיש מעגל גדול או שווה ל-51 הוא בערך ln 2.
    הסיכוי שאין מעגל כזה הוא 1 פחות ln 2, כי אם יש מעגל כזה הוא יחיד.
    נניח שנתון שהפתקים חולקו באקראי וכך גם המספר שבוב צריך לחפש (לא מנסים להכשיל אותו).

    עכשיו נניח שאליס לא משתתפת. יש לבוב 50 ניסיונות בלבד.
    הרי אם בוב יבחר 50 קופסאות באקראי, ההסתברות שלו להצליח היא בדיוק 0.5 לא משנה איזה מהן יבחר.
    נניח שבוב ילך לפי השיטה שמתוארת בפתרון החידה:
    מצד אחד ההסתברות שיצליח היא 0.5 כי הוא עדיין פותח 50 קופסאות (וגם הוא לא מקבל אינפורמציה כלשהי שעוזרת לו).
    מצד שני ההסתברות היא:
    [ההסתברות שאין מעגל גדול מ-50] כפול 1 + [ההסתברות שיש מעגל כזה] כפול חצי.
    זה יוצא בערך 0.65 וזה שונה מחצי… משהו כאן לא הגיוני… איפה טעיתי?

    נניח שאליס משתתפת אבל אסור לה להחליף פתקים, מותר לה רק לומר אם יש מעגל שגדול מ-50 או לא ואסור לה לשקר. (נותנים לבוב מספר באופן אקראי רק אחרי שאליס מסיימת.)
    אם היא אומרת שלא קיים, הרי שבוב יצליח בוודאות.
    אם היא אומרת שקיים מעגל כזה: מה כדאי לבוב לעשות?? אם הוא בוחר 50 קופסאות באקראי הסיכוי שלו הוא 50%? אם הוא משתמש באותה שיטה בפתרון החידה הסיכוי שלו יורד לכ-28% או לכ-30% או נשאר 50%? יש שיטה שבה הסיכוי שלו יהיה גבוה יותר מ-50%? מה הוא צריך לעשות כדי שהסיכוי שלו יהיה מקסימלי? זה מזכיר לי את בעיית מונטי הול.

    אני מבולבל…

  26. יצאתי חומוס…
    הטעות שלי שהנחתי ההסתברות להיכשל ב"שיטה" כאשר יש מעגל באורך 51 או יותר היא 0.5 אבל למעשה מחישוב ישיר היא 1 חלקי (2 כפול ln 2) שזה בערך 0.721. זה קצת יותר מ-ln 2 שהוא בערך 0.693.

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

    אם אליס אומרת לבוב שיש מעגל באורך 51 ומעלה, כמובן שעדיף לו לבחור 50 תיבות באקראי ולזכות בסיכוי של 50% מאשר ללכת לפי השיטה שנותנת לו סיכוי של כ-28% בלבד. אבל האם יש לו אסטרטגיה לשפר את הסיכויים מעבר ל-50%?

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *