100 людей стоять у ряд один за одним і дивляться вперед. Кожному вдягають чорний або білий капелюх. Кожен бачить усі капелюхи попереду себе, але не свій і не тих, хто позаду. Починаючи із заднього, кожен уголос називає одне слово: «чорний» або «білий». Хто назвав колір свого капелюха, виграє. Домовитися про стратегію можна заздалегідь. Скільки людей гарантовано виграють?
Здається, що краще за «половину» не вийде: задній підказує сусідові, і так парами. Але задній може сказати одне слово про всіх одразу: чи парна кількість чорних капелюхів, які він бачить. Після цього кожен наступний точно знає свій колір. Ризикує лише задній, тож гарантовано виграють 99, а в середньому 99,5.
Класична задача зі співбесід програмістів: Вільям Паундстоун наводить її у книжці про головоломки на співбесідах у Google (2012). Не плутайте її із задачею про 100 в'язнів і коробки: там люди не можуть нічого передати одне одному, а тут кожне слово чують усі.
100 людей стоять один за одним і дивляться вперед. Пронумеруємо їх ззаду: людина 1 стоїть позаду всіх, людина 100 попереду.
Кожному вдягають чорний або білий капелюх, навмання. Може бути будь-яке поєднання: усі чорні, усі білі, будь-що між ними.
Кожен бачить усі капелюхи попереду себе. Свого капелюха і тих, хто позаду, не бачить. Людина 1 бачить 99 капелюхів, людина 100 не бачить жодного.
Почергово, від людини 1 до людини 100, кожен уголос каже одне слово: «чорний» або «білий». Усі чують усе. Хто назвав колір свого капелюха, виграє.
Люди заздалегідь домовляються про стратегію. Скільки з них можна гарантовано врятувати, хоч які капелюхи їм вдягнуть?
«50: розбитися на пари, задній називає колір сусіда попереду»
Хтось каже «0», бо свого капелюха ніхто не бачить. Насправді гарантовано виграють 99. Ризикує лише людина 1, і в неї шанс 1/2. Хитрість у тому, що її слово несе інформацію не про одного сусіда, а про весь ряд.
100 людей, найкраща стратегія, найгірші капелюхи. Зафіксуйте, скільки з них, на вашу думку, гарантовано назвуть свій колір.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Слово людини 1 чують усі 99 людей попереду. Шкода витрачати його на підказку лише одному сусідові.
Нехай людина 1 скаже одне слово про весь ряд одразу: парна чи непарна кількість чорних капелюхів, які вона бачить.
Людина 2 знає парність, яку побачила людина 1, і сама бачить усіх попереду. Чого їй бракує, щоб знати власний колір? І чи може хтось у ряду знати колір людини 1?
Капелюшник знає вашу стратегію і вдягає капелюхи так, щоб виграло якнайменше людей. Можете також вдягнути капелюхи самі: клацніть капелюх, щоб змінити колір, і натисніть «Хай говорять». Під кожним капелюхом прямокутник показує колір, який людина назвала.
–
Тепер капелюхи випадкові, без злого капелюшника. Кожен ряд зі 100 людей розігруємо повністю: люди по черзі чують, бачать і кажуть слово. Стовпчики показують, як часто виграло рівно стільки людей, тонка лінія показує точний розподіл.
«Назвати капелюх попереду» і «навмання» мають однаковий розподіл, тож їхні стовпчики накладаються. Стовпчики стратегії «чет/нечет» обрізано: кожен із двох сягає приблизно 50%.
Слово людини 1 здається марним: свого капелюха вона не знає. Але чують його всі 99 людей попереду, і саме тому воно таке цінне.
Домовленість: «чорний» від людини 1 означає «я бачу непарну кількість чорних капелюхів», «білий» означає парну. Людина 2 бачить ті самі капелюхи, крім свого. Якщо парність у неї вийшла інша, різницю дає її власний капелюх, і він чорний. Далі кожен додає до побаченого ще й «чорні», які вже прозвучали попереду нього в черзі, адже всі ті люди назвали свій колір правильно.
Людина 1 говорить першою, тож нічого не чує, а бачить лише чужі капелюхи. Її слово залежить тільки від них. Капелюшник, який знає стратегію, дивиться, що вона скаже, і вдягає їй протилежний колір. Тому 100 гарантувати не можна, а найбільше можливе середнє дорівнює 99 + 1/2 = 99,5.
У стратегії пар задній у кожній парі витрачає своє слово на сусіда, хоча його чують усі. Кожна така підказка несе один біт про одну людину. Слово «парно чи непарно» теж один біт, але про суму всіх капелюхів одразу. Кожен, хто стоїть попереду, знає всі доданки, крім одного, і цього досить.
Це індукція: людина 2 точно знає свій колір, тож її слово правдиве. Тоді людина 3 знає все про капелюхи 2 і 4–100, і так далі до людини 100, яка не бачить жодного капелюха, але знає свій.
У парах задній вгадує з шансом 1/2, передній завжди: 50 · 1/2 + 50 = 75. Навмання кожен вгадує з шансом 1/2: 100 · 1/2 = 50. У стратегії чет/нечет 99 вгадують завжди, а людина 1 з шансом 1/2.
| ⊕ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
a ⊕ b ⊕ b = a
білий = 0, чорний = 1
Запишіть білий як 0, чорний як 1. Парність суми дорівнює XOR усіх цифр: 1 ⊕ 1 = 0, бо дві одиниці дають парне число. Головна властивість: XOR скасовує сам себе, b ⊕ b = 0. Тому з XOR усіх капелюхів можна «вийняти» відомі, і залишиться невідомий: hj = s ⊕ (почуте) ⊕ (побачене).
Те саме працює для k кольорів, якщо пронумерувати їх 0, 1, …, k − 1 і рахувати суму за модулем k, тобто остачу від ділення на k. Людина 1 називає колір із номером «сума всіх, кого вона бачить, mod k». Гарантовано знову виграють n − 1.
Кольори пронумеровано 0, …, k − 1, hi означає колір людини i. Людина 1 бачить капелюхи 2…n і називає колір s, їхню суму за модулем k.
Людина j чула s і правильні кольори людей 2…j − 1, а бачить капелюхи j + 1…n. Невідомий лише її власний.
Два кольори: віднімання за модулем 2 збігається з додаванням, і формула стає ланцюжком XOR.
Підсумок: гарантовано виграють усі, крім людини 1, а вона вгадує з шансом 1/k.
Для 100 людей і двох кольорів це 99 гарантованих переможців і 99,5 у середньому. Більше не можна: людина 1 нічого не знає про свій капелюх за жодної стратегії.
Капелюхи в ряд відкривають двері в три світи. У математиці вони ведуть до арифметики остач і кодів Геммінга. У логіці показують, як один контрольний біт береже всіх інших. А на практиці той самий XOR відновлює втрачений диск і ловить хибну цифру в номері картки.
Математика
Пронумеруйте кольори числами 0, 1, …, k − 1. Людина 1 додає номери всіх капелюхів, які бачить, бере остачу від ділення на k і називає колір із цим номером. Кожен наступний віднімає від неї почуте й побачене, і остача дає номер його кольору.
Гарантія та сама: n − 1. Зате шанс людини 1 падає до 1/k, тож середнє дорівнює n − 1 + 1/k. Для 100 людей і трьох кольорів це 99⅓. Остачі за модулем k утворюють групу: у кожного числа є протилежне, і саме тому відомі доданки можна відняти.
Кожен бачить два чужі капелюхи. Усі одночасно кажуть «чорний», «білий» або «пас». Команда виграє, якщо хоч один вгадав і ніхто не помилився. Оберіть правило, однакове для всіх.
Здається, що більше 1/2 тут не вийде: кожен окремий вгадує з шансом 1/2. Але правило «бачу два однакові, називаю протилежний, інакше пас» виграє в 6 розкладах із 8, тобто з шансом 3/4. Програє воно лише тоді, коли всі три капелюхи однакові, і тоді помиляються всі троє разом.
Кожна вгадка правильна в одному розкладі і хибна в сусідньому, де змінено лише цей капелюх. Тож правильних і хибних вгадок порівну. Для перемоги досить однієї правильної, а один програшний розклад може «поглинути» до n хибних. Звідси межа: шанс не більший за n/(n + 1). Для n = 3 це 3/4, і повний перебір усіх 81³ = 531 441 комбінацій правил підтверджує, що краще не буває.
Для n = 2m − 1 межу досягає код Геммінга, той самий, що в задачі про отруєне вино: 7 гравців виграють у 112 розкладах зі 128 (7/8), 15 гравців у 30 720 із 32 768 (15/16). Кожен перевіряє, чи не утворять капелюхи кодове слово, і якщо так, називає колір, що це слово руйнує.
Логіка
10 людей, стратегія чет/нечет. Клацніть людину, і вона назве не той колір, що вирахувала. Можна кількох.
Слово людини 1 нічого не каже про неї саму. Це контрольний біт: парність усіх інших капелюхів. Якщо відома сума і всі доданки, крім одного, той один відновлюється. Решта стратегії це просто 99 разів застосована ця думка.
Цікавий наслідок: одна обмовка не валить ряд. Якщо людина j із середини ряду назве хибний колір, людина j + 1 теж помилиться, але її хибне слово скасує першу помилку, і всі далі знову праві. Одна помилка коштує рівно двох людей. Перевірте це клацанням.
Практика
Одна смуга масиву: байти з дисків даних A, B, C і байт парності P = A ⊕ B ⊕ C. У RAID 5 парність для різних смуг лежить на різних дисках, але арифметика та сама. Оберіть диск, який «згорить».
Найпростіший захист даних це біт парності: до групи бітів додають ще один, щоб кількість одиниць стала парною. Якщо один біт зіпсувався, парність не зійдеться, і помилку видно. Так перевіряли символи в послідовних лініях зв'язку і пам'ять у старих комп'ютерах.
RAID 5 робить крок далі. Диск, який вийшов з ладу, відомий: це як людина в ряду, яка знає, що невідомий саме її капелюх. Тоді парність не лише ловить помилку, а й відновлює втрачене: B = A ⊕ C ⊕ P. Масив переживає втрату будь-якого одного диска, витрачаючи на захист лише один диск, а не дзеркальну копію кожного.
Остання цифра номера банківської картки контрольна, як слово людини 1. Її обирають так, щоб особлива сума всіх цифр ділилася на 10. Ідучи справа наліво, кожну другу цифру подвоюють, а якщо вийшло більше 9, віднімають 9. Для стандартного прикладу 79927398713 сума дорівнює 70, тож номер правильний.
Це сума за модулем 10, як сума кольорів за модулем k. Вона ловить будь-яку одну хибну цифру і майже будь-яку перестановку двох сусідніх. Не помічає лише 09 ↔ 90. Алгоритм запатентував інженер IBM Ганс Петер Лун, і ним досі перевіряють номери карток, наприклад у формах оплати, ще до звернення до банку.
Гру, де гравці вгадують водночас і можуть пасувати, описав Тодд Еберт у своїй докторській дисертації (Каліфорнійський університет у Санта-Барбарі, 1998). Розійшлася вона, коли Еберт, уже викладач інформатики в Ірвайні, дав студентам за додаткові бали версію на сімох, «задачу про сімох в'язнів».
10 квітня 2001 року Сара Робінсон написала в «The New York Times» статтю «Why Mathematicians Now Care About Their Hat Color» про те, як головоломка Еберта несподівано вивела на теорію кодів.
Гендрік Ленстра і Гадієль Серуссі у статті «On Hats and Other Covers» (конференція IEEE ISIT, Лозанна, липень 2002) пов'язали найкращі стратегії гри з покривальними кодами: множинами, з яких до будь-якого розкладу можна дійти, змінивши щонайбільше один капелюх.
Ганс Петер Лун з IBM подав заявку на «Computer for Verifying Numbers» 1954 року, а патент США 2 950 048 отримав 1960-го. Пристрій перевіряв номери саме за тим алгоритмом, яким сьогодні перевіряють номери карток.
Девід Паттерсон, Гарт Гібсон і Ренді Кац з Берклі опублікували статтю «A Case for Redundant Arrays of Inexpensive Disks (RAID)». У ній описано кілька рівнів RAID, зокрема RAID 5, де блоки парності розкидано по всіх дисках.
Якщо людей нескінченно багато, а кожен бачить усіх попереду, то за аксіоми вибору існує стратегія, з якою помиляються лише скінченно багато людей. Її 2004 року знайшли Ґабай і О'Коннор, аспіранти Корнелла. Цю й інші дивні версії розібрали Крістофер Гардін і Алан Тейлор у книжці «The Mathematics of Coordinated Inference» (2013).
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.