בעיה לגבי אסירים וכובעים שצריך לקבוע את צבעם
נופש / / December 31, 2020
מערכת הסגירה רואה את כל הכובעים, אך יכולה לומר רק "שחור" או "לבן", ובו זמנית ליידע את כולם על המידע הנסתר. האסירים אינם יודעים את המספר הכולל של מכסי שחור ולבן, יש יותר משתי אפשרויות אפשריות. אך הן מוגבלות לשתי גרסאות בלבד כשמדובר במושג זוגיות: המספר יכול להיות שווה או אי זוגי.
המפתח לפתרון הבעיה הוא זה: האסירים מסכימים כי המגיב הראשון יגיד, למשל, "שחור", אם הוא רואה מספר אי זוגי של כיפות שחורות מלפנים, ו"לבן "אם הוא רואה מספר זוגי של שחור כובעים.
בואו נסתכל על הדוגמה מהתמונה למעלה. האסיר הגבוה ביותר 1 רואה שלוש כיפות שחורות לפנינו. הוא אומר "שחור" בקול רם. זה נותן לכל השאר את המידע שיש מספר מוזר של כיפות שחורות לפנינו. האסיר הראשון טעה בצבע הכובע שלו, אבל זה בסדר: פעם מותר לענות לא נכון.
אסירה מס '2 רואה לפניה מספר אי זוגי של כיפות שחורות. היא מבינה שהיא לבנה ועונה נכון. האסיר מספר 3 רואה מספר זוגי של כיפות שחורות ומנחש שהוא חובש כיפה שחורה שראו שני השבויים הראשונים.
שבוי מספר 4 שומע את התשובה ומבין שהיא צריכה לחפש מספר זוגי של כיפות שחורות, כי היה שחור מאחורי גבה, אבל היא רואה רק אחת לפניה ומסיקה שכובעה שחור. אסירים מס '5-9 מחפשים מספר מוזר של כובעים שחורים, שהם פשוט רואים, תוך שהם מבינים שהם חובשים כיפות לבנות. התור מגיע לאסיר העשירי. אם האסיר מספר 9 ראה מספר אי זוגי של כיפות שחורות, זה אומר רק דבר אחד - לאסיר מספר 10 יש כיפה שחורה.
כך האלגוריתם הזה יעבוד עבור כל קבוצת רכזות. עבור המשתתף הראשון, ההסתברות לתשובה שגויה היא 50%, אך המידע על זוגיות שווה-מוזרה, שהוא ייתן, יאפשר לשאר השבויים לנחש את צבע הכובע שלהם.
כל מגיב יתחיל להעריך את מספר המכסים השווים והמשונים שלפנינו. אם המספר המחושב במוחו אינו עולה בקנה אחד עם מה שהוא רואה, הרי שכובעו הוא באותו הצבע. בכל פעם במקרה זה, המגיב הבא לוקח בחשבון כי המוזרות השווה של המכסים שנותרו השתנתה כעת.
פאזל זה הוא תרגום לסרטון TED-Ed.