Задача 95 «Penney-Ante»
Волтер Пенні опублікував гру як задачу № 95 у другому томі «Journal of Recreational Mathematics», на сторінці 241.
Кожен гравець обирає трійку кидків монети, наприклад «орел, орел, орел». Монету підкидають, доки одна з трійок не випаде поспіль. Ви обираєте першим, суперник бачить ваш вибір. Якщо ви обрали ООО, а він РОО, який у нього шанс виграти? Зафіксуйте відповідь, а потім перевірте її у грі проти комп'ютера і на мільйоні симульованих партій.
Кожен гравець обирає трійку кидків монети. Монету підкидають, доки одна з трійок не випаде поспіль. Здається, що всі трійки рівні, бо кожна має шанс 1/8. Але РОО випереджає ООО в 7 партіях з 8, і хоч яку трійку ви оберете, суперник знайде відповідь, що виграє щонайменше у 2 партіях з 3.
Цю гру описав Волтер Пенні 1969 року в «Journal of Recreational Mathematics». Правила вміщуються в три рядки, а зіграти з другом можна за п'ять хвилин.
Монета чесна: орел (О) і решка (Р) випадають з однаковим шансом 1/2, і кидки не залежать один від одного.
Трійкою назвемо три результати поспіль у певному порядку. Їх усього вісім: ООО, ООР, ОРО, ОРР, РОО, РОР, РРО, РРР. Будь-які три кидки поспіль дають кожну з них з шансом 1/8.
Ви обираєте трійку першим. Суперник бачить ваш вибір і обирає іншу трійку.
Монету підкидають знову і знову. Виграє той, чия трійка першою з'явиться як три останні кидки. Наприклад, ви обрали ООО, суперник РОО, і випало так:
Після п'ятого кидка останні три дали РОО, і суперник виграв.
Ви обрали ООО, суперник РОО. Який шанс, що виграє суперник?
«Кожна трійка має шанс 1/8, тож це 50 на 50»
Насправді РОО виграє в 7 партіях з 8. Однакова ймовірність трійки у фіксованих трьох кидках нічого не каже про те, яка трійка з'явиться першою. Ба більше, у цій грі немає найкращої трійки: на кожну знайдеться сильніша.
Ви обрали ООО, суперник обрав РОО. Зафіксуйте, з яким шансом, на вашу думку, виграє суперник.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Те, що кожна трійка має шанс 1/8 у трьох фіксованих кидках, нічого не каже про те, яка з'явиться першою. Подумайте, що мусить випасти безпосередньо перед першою появою ООО.
Уявіть, що десь уже випала решка. Чи може після цього ООО з'явитися раніше за РОО? Подивіться, що стоїть на один кидок раніше за перші три орли поспіль.
Подумайте, у якій єдиній ситуації перед першими трьома орлами поспіль немає решки. Як часто так буває?
Наступні раунди показують шанс суперника: гра проти комп'ютера, усі пари трійок і пояснення. Спершу відповісти в раунді 1 чи йти далі?
Ви обрали завжди показувати всі раунди.
Оберіть трійку, і комп'ютер відповість своєю. Підкидайте монету по одному разу, догравайте партію до кінця або зіграйте 100 партій одразу. Потім поміняйтеся ролями: нехай комп'ютер обирає першим, а ви спробуйте його обіграти.
У рядку стоїть трійка першого гравця, у стовпці трійка другого. У клітинці шанс, що першою випаде трійка зі стовпця: точний дріб і результат симуляції. Що темніша клітинка, то вищий шанс. Рамкою позначено найкращу відповідь другого гравця.
Клітинки на перетині трійки з собою порожні. Шанс першого гравця дорівнює 1 мінус число в клітинці.
Тепер без суперника: монету підкидають, доки трійка не з'явиться. Стовпчики показують точне середнє, точки показують середнє 20 000 симульованих очікувань для кожної трійки.
Трійки рівні, якщо дивитися на три фіксовані кидки. Але в грі важливо інше: як трійки накладаються одна на одну й самі на себе. Ось п'ять способів це побачити.
Шар «На пальцях» приховано на всіх задачах.
Якщо серед перших трьох кидків є решка, то перед першою появою ООО обов'язково стоїть решка. Ця решка разом із двома орлами після неї вже утворює РОО, причому на кидок раніше. Тож щойно випала перша решка, ООО програла остаточно.
Стрілка веде від переможця до переможеного, число показує шанс переможця. РОО б'є ООР, ООР б'є ОРР, ОРР б'є РРО, а РРО б'є РОО. Коло замикається, як у грі «камінь, ножиці, папір». Таке відношення називають нетранзитивним: з «А сильніше за Б» і «Б сильніше за В» не випливає «А сильніше за В».
Відповідь закінчується тими двома кидками, з яких починається трійка суперника. Тому вона майже завжди «підстерігає» його трійку: щоб суперник завершив свою, спершу мають випасти її перші два кидки, а перед ними часто вже стоїть потрібний вам перший символ. Перший символ беруть протилежним до середнього, щоб відповідь сама себе не перекривала й не чекала зайвого.
Шар «Строго» приховано на всіх задачах.
У 1000 кидках є 998 вікон по три, і кожна трійка в середньому трапляється 998/8 ≈ 124,75 раза. Але ООО ходить купками: ОООО містить її двічі, ООООО тричі. Коли появи злипаються, між купками лишаються довші проміжки, і на першу появу доводиться чекати довше.
Уявіть, що вже випало ОО. Для ООР третій орел нічого не псує: ви знову маєте ОО і чекаєте на решку. Для ООО решка на цьому місці зводить усе нанівець, і треба починати з нуля. На трійки, що накладаються самі на себе, доводиться чекати довше.
Але час очікування не вирішує дуель. ООО і ООР грають 50 на 50, хоч на них чекають у середньому 14 і 8 кидків: обидві починаються з ОО, і після першого ОО все вирішує наступний кидок.
Провідне число A·B будуємо так:
Формула Конвея: шанси рахуються через чотири провідні числа. Останній рядок підставляє числа з прикладу вище.
Середній час очікування комбінації A: подвоєне A·A.
Джон Конвей знайшов цю формулу й назвав її алгоритмом провідних чисел, але доведення не опублікував. Доведення з'явилися згодом, зокрема мартингальне доведення Шуо-Єнь Роберта Лі (1980) і робота Гібаса й Одлизка (1981). Формула працює для комбінацій будь-якої довжини, якщо жодна не міститься в іншій. За нею сторінка рахує всі точні числа в таблиці раунду 3, а симуляція їх перевіряє.
Що буде, якщо грати комбінаціями з двох чи чотирьох кидків? Як порахувати дуель будь-яких двох комбінацій? І чи працює фокус, коли замість монети беруть колоду карт?
| Перший | Найкраща відповідь | Точно | Симуляція |
|---|
Наберіть комбінації літерами О і Р (або H і T), до 12 символів. Довжини можуть різнитися, але одна комбінація не має містити іншу.
Для кожного k, за якого перші k символів комбінації збігаються з останніми k, додаємо 2k. Сума дорівнює середній кількості кидків до першої появи. На комбінацію довжини n без самоперекриттів чекають у середньому 2n кидків, а на n однакових символів поспіль найдовше: 2n+1 − 2.
Для четвірок перший гравець найкраще захищається комбінацією ОРОО (або РОРР): суперник отримує щонайбільше 9/14. Дж. А. Чірік довів 1992 року, що для довжини k ≥ 4 найкраща комбінація першого гравця така: О, потім Р k−3 рази, потім ОО, і тоді шанси другого гравця (2k−1 + 1) : (2k−2 + 1).
Стів Гамбл і Ютака Нісіяма 2010 року запропонували грати колодою з 52 карт: 26 червоних (♥) і 26 чорних (♠). Карти відкривають по одній. Щойно з'явилася чиясь трійка, її власник забирає всі відкриті карти, і пошук починається заново. Виграє той, хто зібрав більше таких «взяток».
| Перший | Другий | Виграє 1-й | Виграє 2-й | Нічия |
|---|
Числа точні: ми порахували їх перебором усіх станів колоди. Вони збігаються з симуляцією, наведеною у Вікіпедії. Колода посилює перевагу другого гравця, бо взяток багато, а виграє той, хто частіше буває першим.
Волтер Пенні опублікував гру як задачу № 95 у другому томі «Journal of Recreational Mathematics», на сторінці 241.
У жовтневому номері Scientific American за 1974 рік Мартін Ґарднер присвятив колонку «Mathematical Games» парадоксам нетранзитивних відношень. Там він розповів широкому читачеві і про гру Пенні, і про провідні числа Конвея.
Джон Конвей придумав спосіб рахувати шанси будь-якої пари комбінацій через двійкові «провідні числа», але не довів його. Строгі доведення з'явилися на початку 1980-х.
Статистик Бредлі Ефрон придумав чотири кості з такими гранями: 4, 4, 4, 4, 0, 0; шість трійок; 6, 6, 2, 2, 2, 2; 5, 5, 5, 1, 1, 1. Кожна наступна кість програє попередній з шансом 2/3, а перша програє останній. Той самий принцип: хто обирає другим, завжди може взяти сильнішу кість.
На ООО в середньому чекають 14 кидків, на ООР лише 8. Проте в дуелі вони рівні, 50 на 50. А серед четвірок буває й навпаки: ОРРО, на яку чекають у середньому 18 кидків, випереджає РРОО (16 кидків) з шансом 7/12. Хто перший, вирішують перекриття, а не середні часи.
У картковій версії Гамбла й Нісіями другий гравець із ♥♠♠ проти ♠♠♠ виграє 99,49% партій, а програє лише 0,11%. З монетою його шанс був 7/8. Колода перетворює перевагу на майже певну перемогу.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.