צילום: Santeri Viinamäki, Wikimedia Commons (CC BY-SA 4.0)

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

הכללים:

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

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

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

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

השאלה: איזו אסטרטגיה מבטיחה שההכרזה תיעשה בוודאות מלאה - ולא בניחוש?

רמז דק

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

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

רמז עבה

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

עכשיו חשבו: מה הכלל שיבטיח שכל אחד מהתשעים ותשעה "ידווח" על עצמו בדיוק פעם אחת, בלי לדווח פעמיים בטעות?

פתרון

האסטרטגיה

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

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

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

ההכרזה: ברגע שהמונה של הסופר מגיע ל-99, הוא מכריז.

למה זה עובד

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

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

המלכודת של המצב ההתחלתי

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

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

וכמה זמן זה ייקח?

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

הרעיון שמאחורי החידה

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