חידת קופסאות

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

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

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

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

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

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

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

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

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

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