Перша згадка — замітка на дві сторінки
Д. Дж. О'Коннор надрукував парадокс у журналі Mind у замітці «Pragmatic Paradoxes» на сторінках 358–359. Відтоді про нього вийшли десятки статей.
У п'ятницю вчителька каже: «Наступного тижня буде контрольна, в один з п'яти днів, і зранку того дня ви не зможете знати, що вона сьогодні». Учень міркує: не в п'ятницю, бо в четвер увечері я вже знатиму; отже, і не в четвер; і так аж до понеділка. Виходить, такої контрольної не буде. Чи правий він? Дайте свою відповідь, а потім зіграйте за вчительку або за учня.
Може. Учень так повірив своєму доведенню, що нічого не чекав, і контрольна в середу його заскочила. Його ланцюжок тримається лише на першій ланці: п'ятниця справді відпадає. Далі він щоразу спирається на обіцянку, яку сам же оголошує неможливою. А якщо вчителька тягне жереб з понеділка по четвер, то навіть учень, який знає її спосіб і може одного ранку сказати «сьогодні!», вгадує лише раз на чотири тижні.
Цей парадокс відомий з 1940-х років. Найчастіше його розповідають про в'язня, якому суддя обіцяє страту «несподіваного дня», але суть та сама, тож візьмемо мирнішу версію зі школою.
У п'ятницю вчителька каже класу: «Наступного тижня, з понеділка по п'ятницю, буде одна контрольна. І вона буде несподіваною: зранку того дня ви не зможете знати, що вона сьогодні».
Учень міркує: якщо до четверга включно контрольної не буде, то в четвер увечері я знатиму, що вона в п'ятницю. Тоді вона не буде несподіваною. Отже, п'ятниця відпадає.
Тепер останній можливий день — четвер. Якщо до середи контрольної не буде, то в середу ввечері я знатиму, що вона в четвер. Отже, і четвер відпадає. Так само середа, вівторок і понеділок.
Жоден день не годиться, тож несподіваної контрольної бути не може. Учень спокійно йде на вихідні. Хто правий: вчителька, яка пообіцяла, чи учень, який «довів», що обіцянка нездійсненна?
«Кожен крок бездоганний»
Перший крок здається залізним, а кожен наступний повторює попередній. Спробуйте знайти, де саме ланцюжок міг би розірватися, або переконайтеся, що ніде.
Ланцюжок справді переконливий, і тому цей парадокс обговорюють понад 75 років. Але вже другий крок спирається на віру в обіцянку, яку весь ланцюжок «спростовує». Учень, який дійшов висновку «контрольної не буде», стає найлегшою мішенню.
Тобто чи може вона влаштувати контрольну так, щоб учень зранку того дня справді не знав, що вона сьогодні? Оберіть відповідь, перш ніж читати далі.
Відповідь зараховується одразу після кліку. Передумати можна, але в статистику піде перший вибір.
Тут з'явиться відповідь і де саме ланцюжок учня тримається, а де ні.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Почніть з першого кроку учня: чому п'ятниця справді відпадає? Що саме він знає в четвер увечері, якщо контрольної ще не було?
Тепер другий крок. У середу ввечері учень каже: «Лишилися четвер і п'ятниця, п'ятниця відпадає, отже, четвер». На яку обіцянку він тут спирається і чи вірить він їй наприкінці свого міркування?
Уявіть, що учень повністю повірив своєму висновку. Чого він чекатиме в понеділок, вівторок чи середу зранку?
Наступні раунди показують, хто правий: гра за вчительку і за учня, тисячі тижнів у симуляції і пояснення. Спершу відповісти в раунді 1 чи йти далі?
Ви обрали завжди показувати всі раунди.
Зробімо з оголошення гру. Учень може одного ранку тижня сказати «сьогодні контрольна!». Вгадав — контрольна не несподівана. Помилився — більше вгадувати не можна. А якщо контрольної не було до п'ятниці, то в п'ятницю зранку він знає й так. Несподіванка — це контрольна вранці, коли учень не сказав «сьогодні», і не в п'ятницю. Зіграйте за вчительку проти учня-програми, а потім навпаки.
Задайте звичку вчительки: як часто вона ставить контрольну на кожен день. Комп'ютер проживе 10 000 тижнів з двома учнями. Хитрий учень вивчив цю звичку і щотижня каже «сьогодні!» в найімовірніший день з понеділка по четвер. Переконаний учень повірив своєму доведенню і не чекає контрольної зовсім.
Висота стовпчика показує, яка частка тижнів мала контрольну в цей день; заповнена частина — тижні, коли учень був заскочений. Ліві стовпчики — хитрий учень, праві — переконаний. Переконаного учня заскочує кожен день, крім п'ятниці. Хитрого не заскочує п'ятниця і той день, на який він ставить, тож вчительці вигідно розмазати контрольну рівно по понеділку–четвергу: тоді хоч який день він обере, вгадає лише в чверті тижнів.
Після вашої відповіді тут з'явиться код симуляції, який можна запустити в себе.
Та сама симуляція коротко і без бібліотек. JavaScript запускається в консолі браузера (F12) або в Node, Python потребує лише стандартної бібліотеки.
// Несподівана контрольна: 100 000 тижнів. Учень може один раз зранку сказати «сьогодні!»
const N = 100000, DAYS = ['Пн', 'Вт', 'Ср', 'Чт', 'Пт'];
const pick = w => { let r = Math.random() * w.reduce((s, x) => s + x, 0); return w.findIndex(x => (r -= x) < 0); };
function weeks(teacher, call) { // call(): день, на який учень каже «сьогодні!», або -1
let surprise = 0;
const byDay = DAYS.map(() => [0, 0]); // [контрольних, несподіваних] за днями
for (let i = 0; i < N; i++) {
const t = pick(teacher), c = call();
const s = t !== c && t !== 4; // несподівано: не вгадав і це не п'ятниця
byDay[t][0]++; if (s) { byDay[t][1]++; surprise++; }
}
return { rate: surprise / N, byDay };
}
const even4 = [1, 1, 1, 1, 0], even5 = [1, 1, 1, 1, 1];
const r1 = weeks(even4, () => Math.floor(Math.random() * 4));
console.log('Вчителька: жереб Пн–Чт; учень: жереб Пн–Чт', (100 * r1.rate).toFixed(1) + '%', 'точно 75%');
const r2 = weeks(even4, () => 0);
console.log('Те саме, учень завжди каже в понеділок', (100 * r2.rate).toFixed(1) + '%', 'точно 75%');
const r3 = weeks(even5, () => 0);
console.log('Вчителька: жереб Пн–Пт; учень каже в понеділок', (100 * r3.rate).toFixed(1) + '%', 'точно 60%');
const r4 = weeks(even5, () => -1);
console.log('Жереб Пн–Пт, учень вірить, що контрольної не буде', (100 * r4.rate).toFixed(1) + '%', 'точно 80%');
console.log('Частка несподіваних за днями (останній рядок):',
r4.byDay.map(([n, s], d) => DAYS[d] + ' ' + (n ? (100 * s / n).toFixed(0) : 0) + '%').join(' '));
# Несподівана контрольна: 100 000 тижнів. Учень може один раз зранку сказати «сьогодні!»
import random
N = 100_000
DAYS = ["Пн", "Вт", "Ср", "Чт", "Пт"]
def weeks(teacher, call): # call(): день, на який учень каже «сьогодні!», або -1
surprise = 0
by_day = [[0, 0] for _ in DAYS] # [контрольних, несподіваних] за днями
for _ in range(N):
t = random.choices(range(5), weights=teacher)[0]
c = call()
s = t != c and t != 4 # несподівано: не вгадав і це не п'ятниця
by_day[t][0] += 1
if s:
by_day[t][1] += 1
surprise += 1
return surprise / N, by_day
even4, even5 = [1, 1, 1, 1, 0], [1, 1, 1, 1, 1]
r1, _ = weeks(even4, lambda: random.randrange(4))
print("Вчителька: жереб Пн–Чт; учень: жереб Пн–Чт", f"{r1:.1%}", "точно 75%")
r2, _ = weeks(even4, lambda: 0)
print("Те саме, учень завжди каже в понеділок", f"{r2:.1%}", "точно 75%")
r3, _ = weeks(even5, lambda: 0)
print("Вчителька: жереб Пн–Пт; учень каже в понеділок", f"{r3:.1%}", "точно 60%")
r4, by_day = weeks(even5, lambda: -1)
print("Жереб Пн–Пт, учень вірить, що контрольної не буде", f"{r4:.1%}", "точно 80%")
print("Частка несподіваних за днями (останній рядок):",
" ".join(f"{DAYS[d]} {100 * s / n if n else 0:.0f}%" for d, (n, s) in enumerate(by_day)))
Про цей парадокс написано близько сотні статей, і філософи досі сперечаються про найкраще формулювання розв'язку. Але головне можна побачити на пальцях: перший крок учня правильний, а другий уже ні.
Шар «На пальцях» приховано на всіх задачах.
Учень не може водночас вірити обіцянці, щоб викреслювати дні, і не вірити їй, щоб зробити висновок. Це коротка версія. Про те, чому філософам знадобилося стільки статей, — у шарі «Глибше».
У четвер увечері учень знає, що контрольна в п'ятницю, бо в тижні просто не лишилося інших днів. Тут не потрібна жодна віра.
У середу ввечері лишаються два дні. Що п'ятниця «не годиться», каже лише обіцянка вчительки. Тобто «отже, четвер» учень не знає, а виводить з довіри до вчительки. Якщо вчителька таки поставить контрольну на четвер, учень, який довіряв, угадає. А учень, який за своїм же ланцюжком довіру втратив, — ні.
Учень закінчив своє доведення словами «несподіваної контрольної не буде» і пішов на вихідні спокійним. Це найгірше, що він міг зробити. Хто нічого не чекає, того заскочує будь-що.
Вчительці навіть не треба хитрувати: досить будь-якого дня, крім п'ятниці. А якщо учень розумніший і щотижня ставить на якийсь день, раунди 2 і 3 показують, що жереб з понеділка по четвер усе одно лишає йому лише один шанс з чотирьох.
Шар «Строго» приховано на всіх задачах.
| Контрольна ↓ · учень каже «сьогодні» → | Пн | Вт | Ср | Чт | Пт |
|---|
«Н» означає несподіванку, «·» — учень знав. У кожному стовпці з понеділка по четвер рівно одна «·» серед перших чотирьох рядків: на який день учень не постав би, він ловить лише контрольну саме цього дня. Рядок п'ятниці весь з крапок: там учень знає завжди.
Вчителька. Ставить контрольну на понеділок, вівторок, середу чи четвер, кожен з імовірністю 1/4, і ніколи на п'ятницю. Хоч на який день поставить учень, він угадає з імовірністю 1/4, тож несподіванка буде з імовірністю 3/4. Кращого вчительці не досягти.
Учень. Тягне свій жереб з понеділка по четвер. Тоді хоч який день обере вчителька, учень знає його щонайменше з імовірністю 1/4, а п'ятницю знає завжди. Тож і вчителька не може примусити несподіванку частіше, ніж 3 з 4.
Обидві гарантії збігаються, тож 3/4 і є ціною гри. Висновок учня «ні разу» — це не ціна гри, а її найгірший для вчительки варіант, який вона просто не мусить обирати. Виключає вона лише п'ятницю.
Нехай у тижні n днів, і учень може k разів зранку сказати «сьогодні!». Останній день вчителька не бере. Якщо вона тягне жереб з перших n − 1 днів, а учень ставить на k різних з них, то він угадує з імовірністю k/(n − 1). Ціна гри:
Для п'яти днів і однієї спроби:
Чому учню не допомагає те, що він щодня бачить, чи була контрольна? Єдина нова інформація за тиждень — «ще не було», і вона нічого не підказує наперед: план «скажу в середу, якщо до середи нічого не буде» і є просто ставкою на середу. Тож будь-яка стратегія учня зводиться до вибору k днів. Ми перевірили цю формулу точним перебором для n від 2 до 8 і симуляцією 100 000 тижнів.
Шар «Глибше» приховано на всіх задачах.
Уперше парадокс надрукував британський філософ Д. Дж. О'Коннор 1948 року в журналі Mind, у замітці «Pragmatic Paradoxes». Найранішою відомою версією математик Тімоті Чоу вважає «раптові навчання» Леннарта Екбома. 1951 року Майкл Скрівен там само в Mind описав парадокс у сучасному вигляді, а 1953 року Віллард Квайн відповів статтею «On a so-called paradox».
Версію з в'язнем, якому суддя обіцяє страту несподіваного дня, широко відомою зробив Мартін Ґарднер: колонка в Scientific American у березні 1963 року, а 1969 року книжка «The Unexpected Hanging and Other Mathematical Diversions». 1998 року Чоу у статті для American Mathematical Monthly нарахував майже сотню публікацій про цей парадокс.
Квайн пішов далі за наш розбір. На його думку, учень не може знати навіть у четвер увечері, що контрольна в п'ятницю. Чесно йому лишаються дві можливості: або контрольна завтра, або вчителька помилилася чи збрехала. Поки друга можливість відкрита, учень лише вірить, а не знає.
У нашій грі ми зарахували п'ятницю як «учень знає», щоб правила були простими. Квайн же каже, що обіцянка вчительки могла б справдитися навіть у п'ятницю. Чоу підсумовує: суперечка не про арифметику днів, а про те, що саме означає «знати» про майбутнє, і досі немає згоди, яке формулювання найкраще.
Звичайна обіцянка каже щось про світ: «контрольна буде в середу». Ця ж каже про те, що учень знатиме, почувши саме її. Через це її правдивість залежить від того, чи учень їй вірить, а віра залежить від правдивості. Так само влаштоване «це речення хибне».
1960 року логіки Девід Каплан і Річард Монтеґю у статті «A paradox regained» звели несподівану страту до чистої логіки знання і отримали «парадокс знавця», родича теореми Ґеделя. А Реймонд Смалліан у книжці «Forever Undecided» (1987) веде читача від головоломок до теореми Ґеделя і розбирає по дорозі несподіваний іспит. У дусі його лицарів і брехунів: лицар каже «ти ніколи не зможеш довести, що я лицар». Якщо він справді лицар, то ви маєте правдиве твердження, яке не можете довести.
Наша гра з раунду 2 — це парадокс, перекладений мовою теорії ігор. Чоу помітив, що міркування учня схоже на зворотну індукцію у повторюваній дилемі в'язня, а 1998 року філософ Елліот Собер надрукував у журналі Synthese статтю з промовистою назвою «To give a surprise exam, use game theory».
Мова ігор знімає парадокс так: питання «чи може контрольна бути несподіваною напевно?» має відповідь «ні», бо проти будь-якого фіксованого дня є учень, що на нього поставить. Але питання «як часто?» має відповідь «3 з 4», і для цього вчительці досить жеребу.
Змінюйте кількість днів і кількість спроб учня і дивіться, як часто вчителька все одно заскочить. Потім від чисел до ідеї зворотної індукції, яка ламається не лише в школі, і до того, як несподіванку роблять у реальних перевірках.
Хай який довгий тиждень, останній день вчителька віддає без бою: там учень знає. Решта n − 1 днів ділиться між жеребом вчительки і k ставками учня, тож несподіванка виходить з імовірністю (n − 1 − k)/(n − 1).
З двома днями й однією спробою учень справді непереможний: у перший день каже «сьогодні», а другий знає і так. Тут ланцюжок учня має лише одну ланку, і вона правильна. А на місяць з 20 навчальних днів одна спроба вгадує лише 1 раз з 19.
Учень міркував від кінця: спершу останній день, потім передостанній і так до початку. Це зворотна індукція, головний інструмент теорії ігор для ігор, що мають кінець. Іноді вона працює бездоганно: так розв'язують задачу про піратів і золото, і так само день за днем міркують мешканці острова блакитнооких. Там кожен крок спирається лише на те, що всі справді знають.
Але коли кожен крок вимагає вірити, що й інший гравець міркуватиме так само до самого кінця, ланцюжок стає крихким, як у нашого учня.
Гра «стоножка» (Роберт Розенталь, 1981). Двоє по черзі вирішують: забрати більшу частину купки грошей чи передати хід, і купка росте. Зворотна індукція каже: перший гравець має забрати одразу. В експерименті Річарда Маккелві й Томаса Палфрі 1992 року так майже ніхто не робив, і гра тривала довше, а купка росла.
Парадокс мережі магазинів (Райнгард Зельтен, 1978). Мережа з магазинами у 20 містах і в кожному місті конкурент, що вирішує, чи заходити. Зворотна індукція каже, що мережі ніколи не варто влаштовувати цінову війну, бо в останньому місті це вже нікого не налякає, а отже, і в передостанньому… Сам Зельтен писав, що, граючи за мережу, він би цьому висновку не послухався і відлякував би конкурентів.
Скінченна дилема в'язня. Якщо гравці знають, скільки буде раундів, зворотна індукція каже зраджувати з першого ж. А в турнірі Аксельрода найкраще виступила програма, яка починала зі співпраці. Схожий розрив між теорією і людьми — у дилемі мандрівника.
Кожна перевірка, яка має бути несподіваною, грає в нашу гру. Правило з неї просте: розклад, у якому якісь дні після якихось подій стають неможливими, учень (водій, порушник, контрабандист) вирахує так само, як наш учень вирахував п'ятницю. Тому справжні перевірки тягнуть жереб заново щоразу.
| Ситуація | Передбачуваний розклад | Як роблять несподіванку |
|---|---|---|
| Тести на наркотики й алкоголь у водіїв вантажівок у США | Якби водія, якого вже перевірили, більше не обирали до кінця року, після тесту він знав би, що вільний. | Правило 49 CFR 382.305: тести без попередження, дати розкидані по всьому року, і щоразу кожен водій має рівний шанс бути обраним, навіть щойно перевірений. |
| Поліція аеропорту Лос-Анджелеса (LAX) | Пункти перевірки на в'їздах і маршрути кінологів, що повторюються, легко вивчити й обійти. | З 2007 року програма ARMOR, розроблена в Університеті Південної Каліфорнії, розраховує розклад як гру і тягне жереб, де й коли стояти. |
| Раптові самостійні в школі | «Самостійна раз на тиждень, і ніколи двічі поспіль»: після самостійної учні знають, що завтра її не буде. | Наша гра: жереб серед усіх днів, крім тих, які учні вирахують напевно. Чим довший проміжок, тим менше дає одна вдала здогадка. |
Інші задачі, де логіка оголошення про знання дає несподіваний результат: острів блакитнооких і в'язні в капелюхах. А про те, як учасник гри може бути передбачуваним, хоч і старається, — парадокс Ньюкомба.
Д. Дж. О'Коннор надрукував парадокс у журналі Mind у замітці «Pragmatic Paradoxes» на сторінках 358–359. Відтоді про нього вийшли десятки статей.
Мартін Ґарднер розповів про несподівану страту в березневій колонці 1963 року, а 1969 року назвав на її честь цілу збірку: «The Unexpected Hanging and Other Mathematical Diversions».
1998 року Тімоті Чоу нарахував майже сотню публікацій про цей парадокс і зазначив, що згоди щодо найкращого розв'язку досі немає. Здавалося б, задача на п'ять днів.
Вчителька може відкрито сказати класу: «Я тягну жереб з понеділка по четвер». Учні знатимуть її спосіб повністю, і все одно в 3 тижнях з 4 контрольна буде несподіваною.
Якщо контрольна «несподівана» в один з двох днів, а учень може раз сказати «сьогодні», він непереможний: у перший день каже «сьогодні», а другий знає і так. Парадокс починається з трьох днів.
З 2007 року поліція аеропорту Лос-Анджелеса розставляє пункти перевірки й патрулі з собаками за розкладом, який обчислює програма ARMOR, щоб їх не можна було передбачити.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.