שלטון הקמר רוז' בקמבודיה מחליט להוציא להורג עשרה מתמטיקאים, אך מאפשר ליד הגורל להתייצב לצדם. המתמטיקאים מתבשרים על כך שהם יועמדו בטור, כך שכל אחד יוכל לראות את כל מי שלפניו בטור, ועל הראש של כל אחד מהם יונח כובע בצבע כחול או אדום. לאחר מכן הראשון בטור (זה שרואה את כל האחרים) יתבקש לנחש את צבע הכובע שעל ראשו. אם הוא צודק חייו יינצלו ואם הוא טועה, יירו בו בראש במקום. לאחר מכן ימשיכו אל הבא אחריו בטור וכך הלאה. האם המתמטיקאים יכולים למצוא אסטרטגיה שתבטיח שלפחות חלק מהם יישארו בחיים? כמה מהמתמטיקאים אפשר להציל?
פתרון
המתמטיקאי הראשון יאמר אדום אם מספר הכובעים האדומים שחובשים חבריו הוא זוגי, וכחול אם המספר אי-זוגי. המתמטיקאי השני יספור את הכובעים האדומים שהוא רואה לפניו – אם המספר תואם את הכרזתו של הראשון (כלומר הראשון הכריז אדום – ומספר הכובעים זוגי, או שהראשון הכריז כחול – ומספר הכובעים אי זוגי) הרי שעל ראשו כובע כחול, אחרת – הוא חובש כובע אדום. בצורה דומה, ועל פי הכרזות המתמטיקאים הקודמים להם, יכולים גם שאר המתמטיקאים להינצל.
למתמטיקאי הראשון סיכוי של 50% להינצל, וכל תשעת האחרים יינצלו בכל מקרה.
בונוס נוסף, למיטיבי לכת בלבד: מצאו פתרון לסעיף 1 בחידת הבונוס עבור מספר סופי כלשהו של צבעי כובעים, ועבור צבעים שונים.
פתרון
עבור מס' סופי כלשהו של צבעים, נסמן את מס' צבעי הכובעים ב-n, כל צבע יקבל מספר בין 1 ל-n, ואז כל שורת מתמטיקאים היא כמו סדרת מס' טבעיים בין 1 לn. בדומה לפתרון של המקרה הכללי הקודם שתי סדרות יהיו שקולות אם קיים מס' טבעי m כך שלכל מס' טבעי גדול מ-m כל איברי הסדרה זהים. כעת אם המתמטיקאים לא שומעים האחד את השני הם פשוט יאמרו את הצבע שלהם לפי מחלקת השקילות (הם יקבעו מראש סדרה מייצגת לכל מחלקת שקילות ולפיה יעבדו). אם המתמטיקאים כן שומעים האחד את השני, הראשון יביט קדימה על חבריו, יסכום את השינויים במספרים של חבריו מהסדרה המייצגת, יחלק ב-n ויאמר את הצבע שמייצגת השארית, לדוגמה אם הסדרה המייצגת היא: 1,1,1,1... והוא רואה: 1,2,1,1,1.... אז סכום הסטייה הוא 1, חלקי כל n נשאר 1 ונניח 1 זה הצבע אדום, אז הראשון יאמר אדום. השני יסתכל על המשך הסדרה. אם הסטיה של הסדרה מהסדרה המייצגת של מחלקת השקילות היא עדיין 1 הצבע שלו הינו לפי מחלקת השקילות. אחרת הוא יבדוק מה השארית שהוא רואה, וההפרש בין השארית שהוא רואה לשארית שהוא קיבל זה ההפרש בין צבע הכובע שלו לצבע בסדרה המייצגת. מכאן כל מתמטיקאי, נגיד במקום ה-i, סוכם את סכום השאריות שהיו לפניו, ומפחית את הסכום שהיה לפניו (כגזירה מהסדרה המייצגת)מהשארית שהוא רואה לפניו, מכך הוא מקבל את הפער של הצבע שלו מהצבע הi בסדרה המייצגת. באותיות : סטיה לפניו = a. סטייה אחריו=b. צבע שלו בסדרה המייצג=ti0. צבע שלו במציאות=ti. לכן ti=ti0+b-a
עבור מס' אינסופי של צבעים ההוכחה כמעט זהה רק שהצבעים שקולים לכל המס' הטבעיים. נשים לב כי הפעם אין שארית מודולו n אלא רק סכום ההפרשים (כי יש אינסוף מספרים). תמיד יהיה צבע שייצג את הפער מהסדרה המייצגת כי סכום הסטיות תמיד יהיה סופי (נובע מהגדרת הסדרה המייצגת של מחלקת השקילות) והנוסחה מקודם תישאר זהה.
