Математичні парадокси

Блакитноокі острів'яни Гість сказав те, що всі й так знали. Що станеться?На 100-ту ніч поїдуть усі 100 блакитнооких.

На острові живуть 100 людей із блакитними очима і 100 з карими. Дзеркал немає, а говорити про колір очей заборонено. Хто дізнався колір своїх очей, мусить того ж дня опівночі сісти на пором і покинути острів назавжди. Усі острів'яни бездоганні логіки, і всі це знають. Одного дня гість каже при всіх: «Я бачу когось із блакитними очима». Кожен і так це знав. Що станеться?

Здається, що нічого: кожен бачить щонайменше 99 пар блакитних очей. Але гість змінив не те, що знає кожен, а те, що всі знають про знання одне одного. Блакитноокі рахують ночі: якщо блакитнооких, яких я бачу, 99 і вони не поїхали на 99-ту ніч, отже, я теж блакитноокий. На 100-ту ніч поїдуть усі 100 разом.

Вгадати відповідь
Ніч 100усі 100 блакитнооких їдуть разом
99ночей нічого не відбувається
0нових фактів у словах гостя
Умова задачі

Один острів, одна фраза, жодного нового факту

Цю задачу називали найскладнішою логічною головоломкою, її розбирав Теренс Тао, і вона давно стала улюбленицею збірок для підготовки до співбесід. За нею стоїть ціла галузь логіки: як знання одних людей про знання інших змінює те, що вони роблять.

  1. 1

    Острів

    Тут живуть 200 людей: 100 мають блакитні очі, 100 карі. Скільки кого, острів'яни не знають: кожен лише бачить очі всіх інших.

  2. 2

    Табу

    Дзеркал, калюж і фотографій немає. Про колір очей не говорять і не подають знаків. Свої очі ніхто ніколи не бачив.

  3. 3

    Пором

    Щоночі опівночі приходить пором. Хто вдень дізнався колір своїх очей, мусить на ньому поїхати. Вранці всі бачать, хто поїхав.

  4. 4

    Логіки

    Усі острів'яни бездоганно міркують і не помиляються. Правила острова знає кожен, і кожен знає, що всі їх знають.

  5. 5

    Гість

    Одного дня на острів припливає гість і каже при всіх: «Я бачу когось із блакитними очима». Що станеться далі?

Інтуїція підказує

«Нічого: гість не сказав нічого нового»

Кожен бачить щонайменше 99 блакитнооких, тож факт «на острові є блакитноокі» ні для кого не новина. Проте на 100-ту ніч усі 100 блакитнооких поїдуть разом. Новим стало те, що тепер усі знають, що всі знають, що всі знають… і так без кінця.

Припущення

  • Кожен бачить очі всіх інших, але не свої. Скільки на острові блакитнооких, наперед ніхто не знає.
  • Поїхати можна лише тоді, коли знаєш свій колір напевно. Здогадки не рахуються.
  • Гість каже правду, усі чули його слова, і всі знають, що всі чули.
  • Острів'яни не знають, які кольори очей бувають узагалі. Тож людина, яка дізналась «мої очі не блакитні», ще не знає свого кольору.
  • Ніхто не покидає острів інакше, ніж за правилом порому.
Раунд 1 · Вгадайте

Що станеться після слів гостя?

100 блакитнооких, 100 кароких, одна фраза, яку всі й так знали. Оберіть відповідь.

Тут з'явиться розбір вашої відповіді.

Підказки

Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.

Далі розв'язок

Далі пояснення, і в ньому спойлери

Наступні раунди показують, що станеться на острові після слів гостя: гра, точна перевірка всіх островів і пояснення. Спершу відповісти в раунді 1 чи йти далі?

Ви обрали завжди показувати всі раунди.

Раунд 2 · Гра

Змініть слова гостя і спробуйте зламати логіку

Острів поменше. Оберіть, скільки людей мають блакитні і карі очі, і як гість подасть свою новину: усім разом, нікому, кожному пошепки чи всім, крім одного. Гортайте ночі й дивіться, хто поїде. Клацніть острів'янина, щоб побачити острів його очима.

Блакитнооких
Кароких
Що робить гість
–

Журнал ночей

    Раунд 3 · Точна перевірка

    Усі можливі острови, а не випадкові

    Тут не треба кидати кубики: логіку можна перевірити повністю. Для острова з n людей є 2n варіантів, хто з них блакитноокий. Сторінка тримає в пам'яті всі ці «можливі світи», для кожної людини позначає, які світи вона не може розрізнити, і щоночі викреслює світи, що суперечать побаченому на пристані. Так моделюють знання в логіці з часів Кріпке і Гінтікки.

    Островів перевірено
    –
    Винятків із правила «k блакитнооких їдуть на k-ту ніч»
    –
    Без слів гостя поїхало
    –
    Час перевірки
    –

    Рядок k означає «k людей із n мають блакитні очі». У кожній клітинці ніч, коли вперше хтось поїхав, однакова для всіх островів із цим k; «ніколи» перевірено на n + 2 ночі вперед, а далі модель уже не змінюється. Колонка «карі, якщо кольорів лише два» додає припущення, що всі знають: очі бувають тільки блакитні або карі. Острів'янин, що «не чув», пропустив слова гостя, і всі про це знають. Шепіт кожному окремо змінює знання лише того, хто почув щось нове.

    Раунд 4 · П'ять пояснень

    Чому слова, які всі знали, щось змінили

    Почнімо з маленьких островів і піднімемося до 100. А потім подивимося, що саме гість додав до знань острова.

    На пальцяхкартинки, аналогії, маленькі числа

    Шар «На пальцях» приховано на всіх задачах.

    Один блакитноокий

    Вона не бачить жодних блакитних очей

    До гостя?«мої очі можуть бути будь-якими»
    Після слів гостяніч 1«він міг бачити лише мене»

    Якщо блакитноока лише Аня, вона бачить самі карі очі. Гість каже, що бачить блакитні, отже, це її очі. Першої ж ночі вона їде. Для неї слова гостя справді новина, і це єдиний випадок, коли так.

    Двоє блакитнооких

    Мовчання першої ночі теж повідомлення

    Аня й Борис блакитноокі. Аня бачить Бориса і думає: «Якщо мої очі не блакитні, Борис не бачить жодних блакитних очей і поїде першої ночі». Борис думає так само про Аню. Вранці обоє на місці. Отже, кожен із них бачить блакитні очі, а єдині, яких Аня не бачить, це її власні. Другої ночі вони їдуть разом.

    Кароокий Василь бачить двох блакитнооких і чекає до третьої ночі. Але вони поїхали другої, як і мали б, якби його очі були не блакитні. Тож Василь дізнається лише, що він не блакитноокий.

    Будь-яке k

    Кожна тиха ніч піднімає планку на одиницю

    Блакитноокий острів'янин бачить 99 блакитнооких. Він міркує: «Якщо мої очі не блакитні, то їх рівно 99, а 99 блакитнооких, за тією самою логікою, поїдуть на 99-ту ніч». Він чекає. На 99-ту ніч ніхто не їде. Отже, блакитнооких не 99, а 100, і сотий він сам. Так само думають усі 100, тож вони їдуть разом на 100-ту ніч.

    Кароокий бачить 100 блакитнооких і чекав би 100-ї ночі. Вони поїхали саме тоді, тож він дізнався тільки, що його очі не блакитні. Якщо всі знають, що кольорів лише два, він поїде наступної, 101-ї ночі; за нашими правилами він лишається.

    Де помиляється інтуїція

    «Нічого нового» правда про факт, а не про знання

    Глибина «усі знають, що…» до гостя99рівнів при 100 блакитнооких
    Після гостя∞рівнів: спільне знання

    Аргумент «гість нічого не додав» перевіряє лише перший рівень: чи знає кожен факт. Але міркування блакитнооких спирається на сотий рівень: «я знаю, що Аня знає, що Борис знає, що… знає, що є блакитноокі». До гостя цей ланцюжок обривався на 100-му кроці. Після публічної фрази він став нескінченним, і саме тому почався відлік ночей.

    Строготаблиці, графіки, формули

    Шар «Строго» приховано на всіх задачах.

    Що додав гість

    «Усі знають, що всі знають…», але не нескінченно

      Для тих, хто любить формули

      Індукція за кількістю блакитнооких

      Твердження P(k): якщо блакитноокі рівно k людей і фраза гостя є , то всі k їдуть на k-ту ніч, а раніше не їде ніхто.

      P(k):|B|=k⇒tвиїзду=k

      База: при k = 1 блакитноокий не бачить блакитних очей, тож знає, що це він. Крок: блакитноокий бачить k інших; якби він не був блакитним, за P(k) вони поїхали б на k-ту ніч. Вони не поїхали, тож він блакитноокий.

      P(1),P(k)⇒P(k+1)⇒P(100)

      Без гостя: при k блакитнооких «усі знають, що…» правдиве рівно k − 1 разів поспіль. Глибина k уже хибна, а саме її вимагає крок індукції.

      Ejpправдиве⇔j≤k−1

      Узагальнення: якщо гість скаже «я бачу щонайменше m блакитнооких», відлік починається з m, і всі k їдуть на ніч k − m + 1.

      |B|≥m⇒tвиїзду=k−m+1

      Обидві половини потрібні. Без бази індукція не має з чого стартувати: при k = 1 саме фраза гостя дає блакитноокому знання. Без кроку неясно, чому мовчання ночі щось означає: воно означає щось тільки тому, що всі знають, як міркували б інші.

      Глибшеузагальнення, теорія, історія

      Шар «Глибше» приховано на всіх задачах.

      Підтеорія · епістемічна логіка

      Модель Кріпке: острів із трьох людей як куб

      Кожна вершина куба означає можливий світ: хто з трьох людей A, B, C має блакитні очі. Ребро кольору людини з'єднує два світи, які вона не розрізняє: вони відрізняються лише її власними очима. Людина знає твердження, якщо воно правдиве в усіх світах, куди з поточного веде її ребро. Публічна фраза гостя викреслює світ «ніхто не блакитноокий», а кожна ніч розриває ребра між світами, де вранці на пристані видно різне.

      Перший повний аналіз спільного знання дав філософ Девід Льюїс у книжці «Convention» 1969 року, а математично його оформив Роберт Ауман 1976 року в статті «Agreeing to Disagree»: подія є спільним знанням, якщо вона правдива в кожному світі, до якого можна дійти будь-яким ланцюжком ребер.

      E p = KAp ∧ KBp ∧ KCp  ·  C p = E p ∧ E²p ∧ E³p ∧ …
      Раунд 5 · Масштабуємо

      Брудні діти, два генерали і TCP

      Острів'яни відкривають три світи. У математиці глибина знання стає числом, яке можна виміряти. У логіці виявляється, що спільне знання не можна збудувати з ненадійних повідомлень. А на практиці інженери мережевих протоколів, центральні банки і навіть казкарі вже давно живуть із цим фактом.

      Математика

      Брудні діти: тато каже «щонайменше m»

      Клацніть дитину, щоб забруднити або вмити їй чоло. Кожна дитина бачить чужі чола, але не своє. Тато каже, скільки щонайменше дітей у багнюці, і питає знову й знову: «Хто знає, брудне в нього чоло чи ні?» Діти відповідають усі разом.

      Дітей
      Тато каже: «щонайменше…»

      Глибина знання як число

      Кожне «щонайменше» економить питання

      Це та сама задача в шкільному вбранні, її називають задачею про брудних дітей. Тут кольорів лише два, «брудне» і «чисте», і це знають усі, тож за брудними на наступному питанні відповідають і чисті.

      Якщо тато скаже «щонайменше m», то при k брудних вони відповідять «знаю» на питання k − m + 1. Фраза «щонайменше m» робить спільним знанням m рівнів одразу, і рахунок починається з m. Якщо тато мовчить, ніхто ніколи не дізнається: спрацьовує лише глибина k − 1, що вже є в дітей, а потрібна глибина k.

      Логіка

      Два генерали: зламайте план гінців

      Генерали A і B стоять на двох пагорбах. Перемогти можна лише разом. Гінці бігають через долину, де їх може перехопити ворог. План: гінці ходять по черзі A → B → A → …, кожен наступний вирушає лише після прибуття попереднього, а генерал атакує, тільки якщо дочекався всіх гінців, адресованих йому. Оберіть, скільки гінців у плані, і клацніть гінця, якого перехопить ворог.

      Задача про скоординовану атаку

      Останній гінець завжди під загрозою

      Хоч скільки підтверджень у плані, ворогові досить перехопити останнього гінця. Його відправник отримав усе, на що чекав, і атакує, а адресат не дочекався і стоїть. Якщо ж зробити правило обережнішим, удар просто переходить на іншого гінця.

      Джозеф Галперн і Йорам Мозес 1990 року в журналі JACM довели загальне твердження: якщо повідомлення можуть губитися, то жоден скінченний обмін ними не створює спільного знання. Після m доставлених гінців глибина «A знає, що B знає, що…» дорівнює m, але не більше. Острів'янам пощастило: у них була одна публічна фраза, яку всі чули разом.

      Практика

      Трикрокове рукостискання TCP

      Клієнт і сервер домовляються про з'єднання трьома пакетами: SYN, SYN-ACK, ACK. Оберіть, який пакет загубиться вперше.

      Прагматичний компроміс

      TCP не розв'язує задачу генералів, а обходить її

      Після трьох пакетів сервер знає, що клієнт знає, що сервер отримав його запит. Це три рівні, не нескінченність: клієнт, що надіслав ACK, не знає, чи той дійшов. TCP (RFC 793, 1981; тепер RFC 9293) просто не вимагає певності. Клієнт вважає з'єднання відкритим одразу після свого ACK, а якщо ACK загубився, сервер за тайм-аутом повторить SYN-ACK. Помилка можлива, але її виправляють повтором, а не логікою.

      Там, де потрібне саме спільне знання, роблять публічну заяву, як гість на острові. Центральні банки оголошують рішення про ставку на пресконференції для всіх одразу, а не дзвонять кожному банку окремо: важливо, щоб кожен знав, що всі інші теж знають. А в казці Андерсена «Нове вбрання короля» (1837) хлопчик каже вголос те, що всі бачили. Після його слів голого короля бачать усі разом, і вдавати вже не виходить.

      Бонус · Цікаві факти

      Що розповісти друзям

      1953

      Три дами у вагоні

      Джон Літлвуд у книжці «A Mathematician's Miscellany» описав трьох дам у вагоні поїзда: у кожної забруднене обличчя, і кожна сміється з інших. Одна з них раптом розуміє, що брудна і вона сама. Літлвуд поставив цю задачу першою серед улюблених і вже поширив її індукцією на n дам: це те саме міркування, що й в острів'ян.

      1969

      Філософ і правила дорожнього руху

      Девід Льюїс у книжці «Convention» пояснював, як тримаються домовленості на кшталт «їздимо правою смугою». Для цього йому знадобилося спільне знання: кожен знає правило, знає, що інші знають, і так далі.

      1976

      Не можна погодитися не погоджуватися

      Роберт Ауман довів: якщо двоє раціональних людей мають спільні початкові переконання, а їхні оцінки ймовірності події є спільним знанням, то ці оцінки однакові. 2005 року Ауман отримав Нобелівську премію з економіки разом із Томасом Шеллінгом.

      1978

      Ім'я для генералів

      Задачу про ненадійних гінців 1975 року описали Аккоюнлу, Еканадхам і Губер, і в них це були дві банди гангстерів. Генералів у неї привів Джим Ґрей у конспектах про операційні системи баз даних 1978 року.

      1997

      Премія Геделя за знання

      Галперн і Мозес отримали премію Геделя за статтю «Knowledge and Common Knowledge in a Distributed Environment» (JACM, 1990). Вона показала, що мовою знань зручно міркувати про розподілені комп'ютерні системи. 2009 року ця ж стаття отримала ще й премію Дейкстри.

      2008

      Тао і «найскладніша головоломка»

      У середині 2000-х Рендел Манро, автор xkcd, опублікував версію з гуру (її розповів йому незнайомець на вулиці в Бостоні) і назвав її найскладнішою логічною головоломкою у світі. Наша версія з поромом опівночі йде за ним. У лютому 2008 року Теренс Тао виклав задачу у своєму блозі з двома суперечливими аргументами: «гість нічого не змінив» і «через 100 днів поїдуть усі блакитноокі», і запропонував читачам знайти помилку.

      Reasoning About Knowledge

      Рональд Феґін, Джозеф Галперн, Йорам Мозес, Моше Варді

      1995, англійською · розділ 1.1

      Littlewood's Miscellany

      Джон Літлвуд

      1986, англійською · перший розділ, три дами в купе

      Усі книжки →
      Обговорення

      Що ви думаєте?

      Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.

      Рівень «Для всіх» відповідає задачі?

      Дякуємо! Це допоможе точніше ставити рівні.

      Розсилка

      Нові задачі, пояснення й обговорення

      Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.

      Форма підписки з'явиться тут найближчим часом.