Гра Пенні
Гра Пенні — нетранзитивний парадокс, який знайшов Волтер Пенні[fr].
Опис парадоксу вперше опубліковано в жовтні 1969 року в журналі Journal of Recreational Mathematics. Суть парадоксу така: нехай А і Б грають у таку гру — спочатку А вибирає довільну двійкову послідовність (наприклад, з нулів та одиниць) довжини 3 і показує її гравцю Б. Потім Б робить те саме. Далі гравці будують випадкову двійкову послідовність, у якій поява 0 і 1 рівноймовірна (наприклад, кидають монету, вважаючи випадання орла за 1 і решки за 0). Виграє той гравець, чия послідовність зустрінеться в цій випадковій послідовності раніше. Наприклад, нехай гравець А вибрав трійку 001, а гравець Б — трійку 100. Нехай при 5-разовому киданні монети вийшла випадкова послідовність 10100. Останні 3 цифри в ній — 100 — збігаються з трійкою, яку вибрав гравець Б, а трійка А не з'явилася, тому після 5-го кидання монети гравець Б виграє. Парадокс полягає в тому, що для будь-якої трійки гравця А знайдеться така трійка, яка виграє в неї з імовірністю більше 1/2. Тобто немає найсильнішої трійки, для будь-якої трійки знайдеться сильніша, яка виграє в неї з імовірністю, більше половини. Шанси на виграш у гравця Б в гіршому випадку дорівнюють 2/3. Якщо від трійок перейти до четвірок результатів, то шанси гравця Б на виграш стануть ще вищими. Мартін Гарднер з цього поводу пише:
Ситуація ця маловідома, і більшість математиків просто не можуть повірити в неї, коли чують про відкриття Пенні. Це — найкрасивіше обдурювання (якщо обдурювання може бути красивим), розраховане на простака.Оригінальний текст (рос.)Ситуация эта малоизвестна, и большинство математиков просто не могут поверить в неё, когда слышат об открытии Пенни. Это — заведомо самое красивое надувательство (если надувательство может быть красивым), рассчитанное на простака.— Гарднер Мартин. «Путешествие во времени»[1]
У таблиці наведено ймовірність виграшу гравця Б із різними початковими трійками:
- АБ
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) знайшов угорський математик та криптограф Янош Чирік[2].
- ↑ Гарднер Мартин. Путешествие во времени = Time Travel and Other Mathematical Bewilderments. — М. : «Мир», 1990. — С. 75. — 341 с. — ISBN 5-03-001166-8.
- ↑ János A. Csirik. Optimal Strategy for the First Player in the Penney Ante Game // Combinatorics, Probability and Computing. — Cambridge University Press, 1992. — Вип. 1 (3 листопада). — С. 311—321. — DOI:.
- Сергей Мельников. Прыжок через козла // Наука и жизнь. — 1997. — Вип. 5. — С. 62-64. У цьому оповіданні студенти мехмату ДДУ (нині ДНУ — Дніпровський національний університет) отримують залік із фізкультури, скориставшись парадоксом Пенні.
- Daniel Felix. Optimal Penney Ante Strategy via Correlation Polynomial Identities // The electronic journal of combinatorics. — 2006. — Вип. 13.
- Walter Penney. Problem 95: Penney-Ante // Journal of Recreational Mathematics. — 1974. — С. 321.
- Raymond S. Nickerson. Penney Ante: Counterintuitive Probabilities in Coin Tossing // The UMAP Journal. — 2007. — Вип. 4. — С. 503–532. Архівовано з джерела 4 березня 2016.
- J. M. Cargal. Chapter 35. Mixed Chains // Discrete Mathematics for Neophytes: Number Theory, Probability, Algorithms, and Other Stuff. — 1988.
- Roland Backhouse. First-past-the-post Games
- Певзнер П. Лучшее пари для простаков // Квант. — 1987. — № 5. — С. 4—15.