Задача 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. Однакова ймовірність трійки у фіксованих трьох кидках нічого не каже про те, яка трійка з'явиться першою. Ба більше, у цій грі немає найкращої трійки: на кожну знайдеться сильніша.
Ви обрали ООО, суперник обрав РОО. Зафіксуйте, з яким шансом, на вашу думку, виграє суперник.
Тут з'явиться розбір вашої відповіді.
Оберіть трійку, і комп'ютер відповість своєю. Підкидайте монету по одному разу, догравайте партію до кінця або зіграйте 100 партій одразу. Потім поміняйтеся ролями: нехай комп'ютер обирає першим, а ви спробуйте його обіграти.
У рядку стоїть трійка першого гравця, у стовпці трійка другого. У клітинці шанс, що першою випаде трійка зі стовпця: точний дріб і результат симуляції. Що темніша клітинка, то вищий шанс. Рамкою позначено найкращу відповідь другого гравця.
Клітинки на перетині трійки з собою порожні. Шанс першого гравця дорівнює 1 мінус число в клітинці.
Тепер без суперника: монету підкидають, доки трійка не з'явиться. Стовпчики показують точне середнє, точки показують середнє 20 000 симульованих очікувань для кожної трійки.
Трійки рівні, якщо дивитися на три фіксовані кидки. Але в грі важливо інше: як трійки накладаються одна на одну й самі на себе. Ось п'ять способів це побачити.
Якщо серед перших трьох кидків є решка, то перед першою появою ООО обов'язково стоїть решка. Ця решка разом із двома орлами після неї вже утворює РОО, причому на кидок раніше. Тож щойно випала перша решка, ООО програла остаточно.
У 1000 кидках є 998 вікон по три, і кожна трійка в середньому трапляється 998/8 ≈ 124,75 раза. Але ООО ходить купками: ОООО містить її двічі, ООООО тричі. Коли появи злипаються, між купками лишаються довші проміжки, і на першу появу доводиться чекати довше.
Уявіть, що вже випало ОО. Для ООР третій орел нічого не псує: ви знову маєте ОО і чекаєте на решку. Для ООО решка на цьому місці зводить усе нанівець, і треба починати з нуля. На трійки, що накладаються самі на себе, доводиться чекати довше.
Але час очікування не вирішує дуель. ООО і ООР грають 50 на 50, хоч на них чекають у середньому 14 і 8 кидків: обидві починаються з ОО, і після першого ОО все вирішує наступний кидок.
Стрілка веде від переможця до переможеного, число показує шанс переможця. РОО б'є ООР, ООР б'є ОРР, ОРР б'є РРО, а РРО б'є РОО. Коло замикається, як у грі «камінь, ножиці, папір». Таке відношення називають нетранзитивним: з «А сильніше за Б» і «Б сильніше за В» не випливає «А сильніше за В».
Відповідь закінчується тими двома кидками, з яких починається трійка суперника. Тому вона майже завжди «підстерігає» його трійку: щоб суперник завершив свою, спершу мають випасти її перші два кидки, а перед ними часто вже стоїть потрібний вам перший символ. Перший символ беруть протилежним до середнього, щоб відповідь сама себе не перекривала й не чекала зайвого.
Джон Конвей знайшов цю формулу й назвав її алгоритмом провідних чисел, але доведення не опублікував. Доведення з'явилися згодом, зокрема мартингальне доведення Шуо-Єнь Роберта Лі (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, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.