צילום: Jorge Royan, Wikimedia Commons (CC BY-SA 3.0)

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

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

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

אחר כך פונה הסוהר לאסיר שלפניו, ואז לזה שלפניו, וכך עד הראשון בטור.

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

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

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

השאלה: כמה אסירים אפשר להבטיח שישתחררו, ומהי האסטרטגיה?

רמז דק

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

אבל יש לו יתרון שאין לאף אחד אחר: הוא רואה את כל 99 הכובעים. השאלה היא איך לדחוס את כל המידע הזה למילה אחת בת שתי אפשרויות.

רמז עבה

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

התכונה הנכונה היא זוגיות: האם מספר הכובעים השחורים שאני רואה הוא זוגי או אי-זוגי?

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

פתרון

התשובה: 99 אסירים משתחררים בוודאות. האחרון בטור נותר עם סיכוי של חצי - ובממוצע ישתחררו 99.5.

האסטרטגיה שסוכמה מראש:

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

הוא אינו מנסה לנחש את הכובע שלו. הוא מוסר הודעה.

איך פועל האסיר הבא:

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

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

וכל השאר:

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

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

דוגמה קטנה על ארבעה אסירים:

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

הכובעים בפועל: ד' שחור, ג' שחור, ב' לבן, א' שחור.

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

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

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

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

שלושה מתוך ארבעה נחלצו בוודאות, והרביעי נעזר במזל. במאה אסירים המספר הוא 99.

למה אי אפשר להציל את כולם?

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

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