На острові живуть 100 людей із блакитними очима і 100 з карими. Дзеркал немає, а говорити про колір очей заборонено. Хто дізнався колір своїх очей, мусить того ж дня опівночі сісти на пором і покинути острів назавжди. Усі острів'яни бездоганні логіки, і всі це знають. Одного дня гість каже при всіх: «Я бачу когось із блакитними очима». Кожен і так це знав. Що станеться?
Здається, що нічого: кожен бачить щонайменше 99 пар блакитних очей. Але гість змінив не те, що знає кожен, а те, що всі знають про знання одне одного. Блакитноокі рахують ночі: якщо блакитнооких, яких я бачу, 99 і вони не поїхали на 99-ту ніч, отже, я теж блакитноокий. На 100-ту ніч поїдуть усі 100 разом.
Цю задачу називали найскладнішою логічною головоломкою, її розбирав Теренс Тао, і вона давно стала улюбленицею збірок для підготовки до співбесід. За нею стоїть ціла галузь логіки: як знання одних людей про знання інших змінює те, що вони роблять.
Тут живуть 200 людей: 100 мають блакитні очі, 100 карі. Скільки кого, острів'яни не знають: кожен лише бачить очі всіх інших.
Дзеркал, калюж і фотографій немає. Про колір очей не говорять і не подають знаків. Свої очі ніхто ніколи не бачив.
Щоночі опівночі приходить пором. Хто вдень дізнався колір своїх очей, мусить на ньому поїхати. Вранці всі бачать, хто поїхав.
Усі острів'яни бездоганно міркують і не помиляються. Правила острова знає кожен, і кожен знає, що всі їх знають.
Одного дня на острів припливає гість і каже при всіх: «Я бачу когось із блакитними очима». Що станеться далі?
«Нічого: гість не сказав нічого нового»
Кожен бачить щонайменше 99 блакитнооких, тож факт «на острові є блакитноокі» ні для кого не новина. Проте на 100-ту ніч усі 100 блакитнооких поїдуть разом. Новим стало те, що тепер усі знають, що всі знають, що всі знають… і так без кінця.
100 блакитнооких, 100 кароких, одна фраза, яку всі й так знали. Оберіть відповідь.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Не беріться одразу за 100. Зменште острів: що станеться, якщо блакитні очі лише в однієї людини?
Тепер блакитнооких двоє. Кожен чекає, що зробить інший, і ніч, коли ніхто не поїхав, теж дещо повідомляє.
Припустімо, ви вже знаєте, що сталося б на острові з k блакитноокими. Тепер їх k + 1. Що думає кожен із них, коли настає ніч, на яку k людей уже мали б поїхати?
Острів поменше. Оберіть, скільки людей мають блакитні і карі очі, і як гість подасть свою новину: усім разом, нікому, кожному пошепки чи всім, крім одного. Гортайте ночі й дивіться, хто поїде. Клацніть острів'янина, щоб побачити острів його очима.
Тут не треба кидати кубики: логіку можна перевірити повністю. Для острова з n людей є 2n варіантів, хто з них блакитноокий. Сторінка тримає в пам'яті всі ці «можливі світи», для кожної людини позначає, які світи вона не може розрізнити, і щоночі викреслює світи, що суперечать побаченому на пристані. Так моделюють знання в логіці з часів Кріпке і Гінтікки.
Рядок k означає «k людей із n мають блакитні очі». У кожній клітинці ніч, коли вперше хтось поїхав, однакова для всіх островів із цим k; «ніколи» перевірено на n + 2 ночі вперед, а далі модель уже не змінюється. Колонка «карі, якщо кольорів лише два» додає припущення, що всі знають: очі бувають тільки блакитні або карі. Острів'янин, що «не чув», пропустив слова гостя, і всі про це знають. Шепіт кожному окремо змінює знання лише того, хто почув щось нове.
Почнімо з маленьких островів і піднімемося до 100. А потім подивимося, що саме гість додав до знань острова.
Якщо блакитноока лише Аня, вона бачить самі карі очі. Гість каже, що бачить блакитні, отже, це її очі. Першої ж ночі вона їде. Для неї слова гостя справді новина, і це єдиний випадок, коли так.
Аня й Борис блакитноокі. Аня бачить Бориса і думає: «Якщо мої очі не блакитні, Борис не бачить жодних блакитних очей і поїде першої ночі». Борис думає так само про Аню. Вранці обоє на місці. Отже, кожен із них бачить блакитні очі, а єдині, яких Аня не бачить, це її власні. Другої ночі вони їдуть разом.
Кароокий Василь бачить двох блакитнооких і чекає до третьої ночі. Але вони поїхали другої, як і мали б, якби його очі були не блакитні. Тож Василь дізнається лише, що він не блакитноокий.
Блакитноокий острів'янин бачить 99 блакитнооких. Він міркує: «Якщо мої очі не блакитні, то їх рівно 99, а 99 блакитнооких, за тією самою логікою, поїдуть на 99-ту ніч». Він чекає. На 99-ту ніч ніхто не їде. Отже, блакитнооких не 99, а 100, і сотий він сам. Так само думають усі 100, тож вони їдуть разом на 100-ту ніч.
Кароокий бачить 100 блакитнооких і чекав би 100-ї ночі. Вони поїхали саме тоді, тож він дізнався тільки, що його очі не блакитні. Якщо всі знають, що кольорів лише два, він поїде наступної, 101-ї ночі; за нашими правилами він лишається.
Аргумент «гість нічого не додав» перевіряє лише перший рівень: чи знає кожен факт. Але міркування блакитнооких спирається на сотий рівень: «я знаю, що Аня знає, що Борис знає, що… знає, що є блакитноокі». До гостя цей ланцюжок обривався на 100-му кроці. Після публічної фрази він став нескінченним, і саме тому почався відлік ночей.
Кожна вершина куба означає можливий світ: хто з трьох людей A, B, C має блакитні очі. Ребро кольору людини з'єднує два світи, які вона не розрізняє: вони відрізняються лише її власними очима. Людина знає твердження, якщо воно правдиве в усіх світах, куди з поточного веде її ребро. Публічна фраза гостя викреслює світ «ніхто не блакитноокий», а кожна ніч розриває ребра між світами, де вранці на пристані видно різне.
Перший повний аналіз спільного знання дав філософ Девід Льюїс у книжці «Convention» 1969 року, а математично його оформив Роберт Ауман 1976 року в статті «Agreeing to Disagree»: подія є спільним знанням, якщо вона правдива в кожному світі, до якого можна дійти будь-яким ланцюжком ребер.
Твердження P(k): якщо блакитноокі рівно k людей і фраза гостя є спільним знанням, то всі k їдуть на k-ту ніч, а раніше не їде ніхто.
База: при k = 1 блакитноокий не бачить блакитних очей, тож знає, що це він. Крок: блакитноокий бачить k інших; якби він не був блакитним, за P(k) вони поїхали б на k-ту ніч. Вони не поїхали, тож він блакитноокий.
Без гостя: при k блакитнооких «усі знають, що…» правдиве рівно k − 1 разів поспіль. Глибина k уже хибна, а саме її вимагає крок індукції.
Узагальнення: якщо гість скаже «я бачу щонайменше m блакитнооких», відлік починається з m, і всі k їдуть на ніч k − m + 1.
Обидві половини потрібні. Без бази індукція не має з чого стартувати: при k = 1 саме фраза гостя дає блакитноокому знання. Без кроку неясно, чому мовчання ночі щось означає: воно означає щось тільки тому, що всі знають, як міркували б інші.
Острів'яни відкривають три світи. У математиці глибина знання стає числом, яке можна виміряти. У логіці виявляється, що спільне знання не можна збудувати з ненадійних повідомлень. А на практиці інженери мережевих протоколів, центральні банки і навіть казкарі вже давно живуть із цим фактом.
Математика
Клацніть дитину, щоб забруднити або вмити їй чоло. Кожна дитина бачить чужі чола, але не своє. Тато каже, скільки щонайменше дітей у багнюці, і питає знову й знову: «Хто знає, брудне в нього чоло чи ні?» Діти відповідають усі разом.
Це та сама задача в шкільному вбранні, її називають задачею про брудних дітей. Тут кольорів лише два, «брудне» і «чисте», і це знають усі, тож за брудними на наступному питанні відповідають і чисті.
Якщо тато скаже «щонайменше m», то при k брудних вони відповідять «знаю» на питання k − m + 1. Фраза «щонайменше m» робить спільним знанням m рівнів одразу, і рахунок починається з m. Якщо тато мовчить, ніхто ніколи не дізнається: спрацьовує лише глибина k − 1, що вже є в дітей, а потрібна глибина k.
Логіка
Генерали A і B стоять на двох пагорбах. Перемогти можна лише разом. Гінці бігають через долину, де їх може перехопити ворог. План: гінці ходять по черзі A → B → A → …, кожен наступний вирушає лише після прибуття попереднього, а генерал атакує, тільки якщо дочекався всіх гінців, адресованих йому. Оберіть, скільки гінців у плані, і клацніть гінця, якого перехопить ворог.
Хоч скільки підтверджень у плані, ворогові досить перехопити останнього гінця. Його відправник отримав усе, на що чекав, і атакує, а адресат не дочекався і стоїть. Якщо ж зробити правило обережнішим, удар просто переходить на іншого гінця.
Джозеф Галперн і Йорам Мозес 1990 року в журналі JACM довели загальне твердження: якщо повідомлення можуть губитися, то жоден скінченний обмін ними не створює спільного знання. Після m доставлених гінців глибина «A знає, що B знає, що…» дорівнює m, але не більше. Острів'янам пощастило: у них була одна публічна фраза, яку всі чули разом.
Практика
Клієнт і сервер домовляються про з'єднання трьома пакетами: SYN, SYN-ACK, ACK. Оберіть, який пакет загубиться вперше.
Після трьох пакетів сервер знає, що клієнт знає, що сервер отримав його запит. Це три рівні, не нескінченність: клієнт, що надіслав ACK, не знає, чи той дійшов. TCP (RFC 793, 1981; тепер RFC 9293) просто не вимагає певності. Клієнт вважає з'єднання відкритим одразу після свого ACK, а якщо ACK загубився, сервер за тайм-аутом повторить SYN-ACK. Помилка можлива, але її виправляють повтором, а не логікою.
Там, де потрібне саме спільне знання, роблять публічну заяву, як гість на острові. Центральні банки оголошують рішення про ставку на пресконференції для всіх одразу, а не дзвонять кожному банку окремо: важливо, щоб кожен знав, що всі інші теж знають. А в казці Андерсена «Нове вбрання короля» (1837) хлопчик каже вголос те, що всі бачили. Після його слів голого короля бачать усі разом, і вдавати вже не виходить.
Джон Літлвуд у книжці «A Mathematician's Miscellany» описав трьох дам у вагоні поїзда: у кожної забруднене обличчя, і кожна сміється з інших. Одна з них раптом розуміє, що брудна і вона сама. Літлвуд поставив цю задачу першою серед улюблених і вже поширив її індукцією на n дам: це те саме міркування, що й в острів'ян.
Девід Льюїс у книжці «Convention» пояснював, як тримаються домовленості на кшталт «їздимо правою смугою». Для цього йому знадобилося спільне знання: кожен знає правило, знає, що інші знають, і так далі.
Роберт Ауман довів: якщо двоє раціональних людей мають спільні початкові переконання, а їхні оцінки ймовірності події є спільним знанням, то ці оцінки однакові. 2005 року Ауман отримав Нобелівську премію з економіки разом із Томасом Шеллінгом.
Задачу про ненадійних гінців 1975 року описали Аккоюнлу, Еканадхам і Губер, і в них це були дві банди гангстерів. Генералів у неї привів Джим Ґрей у конспектах про операційні системи баз даних 1978 року.
Галперн і Мозес отримали премію Геделя за статтю «Knowledge and Common Knowledge in a Distributed Environment» (JACM, 1990). Вона показала, що мовою знань зручно міркувати про розподілені комп'ютерні системи. 2009 року ця ж стаття отримала ще й премію Дейкстри.
У середині 2000-х Рендел Манро, автор xkcd, опублікував версію з гуру (її розповів йому незнайомець на вулиці в Бостоні) і назвав її найскладнішою логічною головоломкою у світі. Наша версія з поромом опівночі йде за ним. У лютому 2008 року Теренс Тао виклав задачу у своєму блозі з двома суперечливими аргументами: «гість нічого не змінив» і «через 100 днів поїдуть усі блакитноокі», і запропонував читачам знайти помилку.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.