Гра Пенні

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Гра Пенні — нетранзитивний парадокс, який знайшов Волтер Пенні[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].

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Гарднер Мартин. Путешествие во времени = Time Travel and Other Mathematical Bewilderments. — М. : «Мир», 1990. — С. 75. — 341 с. — ISBN 5-03-001166-8.
  2. János A. Csirik. Optimal Strategy for the First Player in the Penney Ante Game // Combinatorics, Probability and Computing. — Cambridge University Press, 1992. — Вип. 1 (4 жовтня). — С. 311—321. — DOI:10.1017/S0963548300000365.

Посилання

[ред. | ред. код]