Гра Пенні — нетранзитивний парадокс, який знайшов .
Опис Опис парадоксу вперше опубліковано в жовтні 1969 року в журналі Journal of Recreational Mathematics. Суть парадоксу така: нехай А і Б грають у таку гру — спочатку А вибирає довільну двійкову послідовність (наприклад, з нулів та одиниць) довжини 3 і показує її гравцю Б. Потім Б робить те саме. Далі гравці будують випадкову двійкову послідовність, у якій поява 0 і 1 рівноймовірна (наприклад, кидають монету, вважаючи випадання орла за 1 і решки за 0). Виграє той гравець, чия послідовність зустрінеться в цій випадковій послідовності раніше. Наприклад, нехай гравець А вибрав трійку 001, а гравець Б — трійку 100. Нехай при 5-разовому киданні монети вийшла випадкова послідовність 10100. Останні 3 цифри в ній — 100 — збігаються з трійкою, яку вибрав гравець Б, а трійка А не з'явилася, тому після 5-го кидання монети гравець Б виграє. Парадокс полягає в тому, що для будь-якої трійки гравця А знайдеться така трійка, яка виграє в неї з імовірністю більше 1/2. Тобто немає найсильнішої трійки, для будь-якої трійки знайдеться сильніша, яка виграє в неї з імовірністю, більше половини. Шанси на виграш у гравця Б в гіршому випадку дорівнюють 2/3. Якщо від трійок перейти до четвірок результатів, то шанси гравця Б на виграш стануть ще вищими. Мартін Гарднер з цього поводу пише:Ситуація ця маловідома, і більшість математиків просто не можуть повірити в неї, коли чують про відкриття Пенні. Це — найкрасивіше обдурювання (якщо обдурювання може бути красивим), розраховане на простака.
У таблиці наведено ймовірність виграшу гравця Б із різними початковими трійками: {| class="wikitable" style="text-align: center" |- ! !000 ||001||010||011||100||101||110||111 |- !000 | ||1/2||2/5||2/5||1/8||5/12||3/10||1/2 |- !001 |1/2|| ||2/3||2/3||1/4||5/8||1/2||7/10 |- !010 |3/5||1/3|| ||1/2||1/2||1/2||3/8||7/12 |- !011 |3/5||1/3||1/2|| ||1/2||1/2||3/4||7/8 |- !100 |7/8||3/4||1/2||1/2|| ||1/2||1/3||3/5 |- !101 |7/12||3/8||1/2||1/2||1/2|| ||1/3||3/5 |- !110 |7/10||1/2||5/8||1/4||2/3||2/3|| ||1/2 |- !111 |1/2||3/10||5/12||1/8||2/5||2/5||1/2||
Щоб відшукати виграшну трійку, у верхньому рядку таблиці знайдіть трійку гравця А, а в її стовпці шукайте найбільше число. У рядку із цим числом у лівому стовпці стоятиме трійка гравця Б, яка виграє проти заданої трійки гравця А з найбільшою ймовірністю. Наприклад, нехай гравець А вибрав трійку 000. У 1 стовпці таблиці шукаємо найбільше число, це 7/8. У лівому стовпчику рядка з числом 7/8 читаємо трійку гравця Б 100, яка виграє проти трійки 000 із ймовірністю 7/8. Дійсно: якщо при киданні монети послідовність не починається на 000, то коли ця трійка вперше з'явиться у випадковій послідовності, їй буде передувати 1, а це означає, що трійка 100 зустрілася раніше, і гравець Б виграв. Трійка 000 виграє проти трійки 100, тільки якщо 000 зустрінеться на початку випадкової послідовності, а ймовірність цього дорівнює 1/8.
Оптимальну стратегію для першого гравця (для будь-якої довжини послідовності не менше 4) знайшов угорський математик та криптограф Янош Чирік.
Див. також Парадокс
Примітки
Посилання У цьому оповіданні студенти мехмату ДДУ (нині ДНУ — Дніпровський національний університет) отримують залік із фізкультури, скориставшись парадоксом Пенні.
Roland Backhouse. First-past-the-post Games