חידת הכובעים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ביטול גרסה - הmod לא נחוץ |
מאין תקציר עריכה |
||
שורה 8:
===מדוע פסק הצחוק?===
[[יוברט פיליפס]] הציג את החידה הבאה: שלושה לוגיקנים נמנמו בשדה. בעת שישנו הגיע אדם שחמד לצון, צבע את פניהם בירוק והעיר אותם. כל אחד מהלוגיקנים, שלא יכול לראות את פני עצמו, פרץ בצחוק למראה הפנים הירוקים של חבריו, אך כעבור רגעים אחדים פסק הצחוק, לאחר שכל אחד מהלוגיקנים הבין שגם פניו נצבעו בירוק. כיצד הבין כל לוגיקן שפניו נצבעו בירוק?
==== פתרון החידה ====
לוגיקן א' מסתכל על חבריו ורואה אותם צוחקים. הוא חושב: נניח שפני נקיות. לוגיקן ב' חושב כמוני, קרי שפניו נקיות. אם גם פניו נקיות, הרי שללוגיקן ג' אין כל סיבה לצחוק. לכן לוגיקן ב' היה מסיק שאם לוגיקן ג' צוחק הרי זה רק משום שגם פניו של לוגיקן ב' צבועות, ומפסיק לצחוק. מהצחוק המתמשך הבין לוגיקן א' שגם פניו צבועות, ולכן לוגיקן ב' סבור שצחוקו של לוגיקן ג' נובע מכך שהוא רואה את פניו הצבועות של לוגיקן א'. לפיכך הבין לוגיקן א' שאין לו סיבה לצחוק. משיקולי סימטריה תושג תוצאה זו לכל אחד מהלוגיקנים, וכולם יפסיקו לצחוק.
הנחת היסוד בפתרונה של חידה זו היא שכל הלוגיקנים חושבים על פי אותם כללי היסק, ולכן כל לוגיקן יכול לנתח את מחשבות חברו. בחידה זו כל הלוגיקנים חושבים במקביל, משום שכל אחד מהם רואה את כל רעיו. בחידת הכובעים המתוארת להלן, החשיבה נעשית בטור, כלומר בכל שלב אדם מפענח את מחשבות כל קודמיו, ודבריו משמשים בסיס לצעד של הבא אחריו.
שורה 24:
===וריאציות של החידה===
לחידה זאת יש מספר רב של וריאציות. המפורסמת שבהן מספרת על תוכנית טלוויזיה שבה עשרה מתמטיקאים יושבים בשורה כך שכל אחד מהם רואה רק את אלו היושבים לפניו. על הראש של כל אחד מהם מולבש כובע מתוך קופסה שבה עשרה כובעים שחורים ורק תשעה כובעים לבנים. החידה מספרת שמנחה התוכנית ניגש אל המתמטיקאי הראשון בשורה, זה שרואה את הכובעים של כל האחרים, ושואל אותו האם הוא יודע את הצבע של הכובע שלו. הוא נותן תשובה שלילית. לאחר מכן ניגשים
כמו בחידת 'מדוע פסק הצחוק', התשובות השליליות של המתמטיקאים שלפניו נותנות למתמטיקאי את המידע להסיק את צבע הכובע שלו. כמו כן גם בחידה זאת ניתן להוכיח באינדוקציה, שתסריט דומה ייתכן גם אילו בשורה יושבים n מתמטיקאים.
וריאציה מפורסמת נוספת היא שני מתמטיקאים שעל הראש של כל אחד מהם מלבישים כובע שעליו רשום מספר, ונאמר להם שהמספרים הרשומים על הכובעים הם מספרים טבעיים עוקבים (לדוגמה 9 ו- 10). עתה ניגשים למתמטיקאי הראשון ושואלים אותו אם הוא יודע את המספר שרשום לו על הכובע, והוא עונה בשלילה. ניגשים לשני, וגם הוא עונה בשלילה, חוזרים לראשון וכך חוזר חלילה עד שבאיזשהו שלב, לאחר רצף ארוך של תשובות שליליות אחד המתמטיקאים עונה בחיוב ומנחש בצורה נכונה את המספר הרשום על הכובע שלו.
== חידת הכובעים והתיאום מראש ==
חידת דומה לחידת המתמטיקאים היושבים בשורה שהוצגה בסעיף הקודם, היא חידה הדורשת [[אלגוריתם]] ומשמשת להדגמת מושגים במדעי המחשב ובתורת הקבוצות.
החידה מספרת על n ([[מספר טבעי]] כלשהו) פרופסורים למתמטיקה נחטפו על ידי סטודנטים נזעמים. הסטודנטים חובשים לראשיהם של הפרופסורים כובעים שחורים ולבנים, והפרופסורים מוצבים בטור, כאשר כל אחד יכול לראות רק את הכובעים של אלה שנמצאים לפניו בטור, אך לא את הכובע שעל ראשו או שעל ראשי הקודמים לו. הפרופסורים צריכים לנחש, כל אחד בתורו - מהראשון בטור (שרואה את כל הכובעים מלבד זה שעל ראשו) לאחרון (שאינו רואה אף כובע) - את צבע הכובע של ראשו. מי שטועה נורה במקום. בהנחה שניתן לפרופסורים זמן לפני כן כדי לגבש אסטרטגיה, מצאו אסטרטגיה שתאפשר לכל הפרופסורים פרט, אולי, לאחד, להינצל.
שורה 81:
המקרה הכללי מכליל את הפתרון של n=2. ראשית הפרופסורים מסכימים ביניהם על מספור, כך שכל פרופסור מקבל מספר בין 0 ל-n-1 וכל צבע אפשרי מקבל מספר בין 0 ל-n-1. נסמן ב-<math>a_k</math> את מספר צבע הכובע של הפרופסור ה-k וב-<math>S</math> את הסכום [[חשבון מודולרי|מודולו n]] של מספרי כל n הכובעים שעל ראשיהם של הפרופסורים: <math>S\equiv \sum_{k=0}^{n-1} a_k \pmod n</math>.
הפרופסור ה-k יכול לסכום את כל מספרי צבעי הכובעים שהוא רואה על n-1 הפרופסורים האחרים וכך לחשב את: <math>b_k \equiv S-a_k \pmod{n}</math>. כעת הפרופסור ה-k ינחש כי צבע הכובע שלו הוא <math>k-b_k</math>.
אחד מהפרופסורים הוא זה שמספרו הוא <math>k=S</math>. הניחוש של הפרופסור הזה יהיה: <math>S-b_S\equiv a_S \pmod{n}</math>, ולכן הפרופסור הזה (ורק הפרופסור הזה) צודק בניחוש שלו.
| |||