חידת הכובעים

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

חידות אינדוקטיביות

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

מדוע פסק הצחוק?

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

פתרון החידה

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

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

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

הכללה באינדוקציה

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

וריאציות של החידה

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

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

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

חידת הכובעים והתיאום מראש

חידת דומה לחידת המתמטיקאים היושבים בשורה שהוצגה בסעיף הקודם, היא חידה הדורשת אלגוריתם ומשמשת להדגמת מושגים במדעי המחשב ובתורת הקבוצות.

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

פתרון

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

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

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

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

מספר בן מניה של פרופסורים

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

הפעם, מעמידים $\aleph _{0}$ (אָלֶף אֶפֶס) פרופסורים למתמטיקה, מהראשון ואילך, בטור, ונניח שכל אחד יכול לראות את כל אינסוף הכובעים שלפניו. מצאו:

1. אסטרטגיה בה יינצלו כמעט כל הפרופסורים (כלומר כולם פרט למספר סופי), כאשר אף אחד לא שומע מה אמרו האחרים.
2. אסטרטגיה בה יינצלו כל הפרופסורים פרט לאחד, כאשר כל אחד שומע מה אמרו האחרים.

פתרון סעיף 1

מספר הפרופסורים הוא בן מניה, לכן שקול למספרים הטבעיים. אם נייצג כובע שחור באמצעות המספר 0 וכובע לבן באמצעות המספר 1, נוכל לייצג סידור כלשהו של כובעים באמצעות פונקציה $f:\mathbb {N} \to \{0,1\}$.

נגדיר יחס שקילות כדלהלן: $f\sim g$ אם ורק אם הסידורים זהים פרט למספר סופי של מקומות. אם כך, כל סידור f מגדיר מחלקת שקילות [f]. תהי A קבוצת מחלקות השקילות. לפי אקסיומת הבחירה קיימת העתקה (פונקציית בחירה) $\phi :A\to \{0,1\}^{\mathbb {N} }$ אשר מתאימה לכל מחלקת שקילות איבר מייצג מאותה מחלקה.

בהינתן סידור כובעים f, כל פרופסור יכול לראות את כל הכובעים שלפניו, כלומר את כל הכובעים פרט למספר סופי של כובעים (של אלה שנמצאים מאחוריו). הסידור f שקול, אם כן, למייצג $\ \phi ([f])$ שנבחר מראש.

כעת, לכל $n\in \mathbb {N}$, הפרופסור במקום ה-n יציין את צבע הכובע שבמקום ה-n בסידור המייצג, כלומר את $\ \phi ([f])(n)$. ראינו כי סידור זה זהה לסידור האמיתי f פרט למספר סופי של כובעים, לכן כל הפרופסורים פרט למספר סופי ינחשו נכון.

פתרון סעיף 2

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

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

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

ניחוש סימולטני

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

פתרון

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

המקרה הכללי מכליל את הפתרון של n=2. ראשית הפרופסורים מסכימים ביניהם על מספור, כך שכל פרופסור מקבל מספר בין 0 ל-n-1 וכל צבע אפשרי מקבל מספר בין 0 ל-n-1. נסמן ב-$a_{k}$ את מספר צבע הכובע של הפרופסור ה-k וב-$S$ את הסכום מודולו n של מספרי כל n הכובעים שעל ראשיהם של הפרופסורים: $S\equiv \sum _{k=0}^{n-1}a_{k}{\pmod {n}}$.

הפרופסור ה-k יכול לסכום את כל מספרי צבעי הכובעים שהוא רואה על n-1 הפרופסורים האחרים וכך לחשב את: $b_{k}\equiv S-a_{k}{\pmod {n}}$. כעת הפרופסור ה-k ינחש כי צבע הכובע שלו הוא $k-b_{k}{\pmod {n}}$.

אחד מהפרופסורים הוא זה שמספרו הוא $k=S$. הניחוש של הפרופסור הזה יהיה: $S-b_{S}\equiv a_{S}{\pmod {n}}$, ולכן הפרופסור הזה (ורק הפרופסור הזה) צודק בניחוש שלו.

לקריאה נוספת

• Martin Gardner, "The 'jump proof' and its similarity to the toppling of a row of dominoes", Mathematical Games, Scientific American, May 1977.