Дуель у романі
У романі Фредеріка Марріета «Мічман Ізі» є дуель утрьох, де кожен учасник цілиться лише в одного визначеного суперника. Обирати ціль, як у нашій задачі, там не можна.
Аня влучає одним пострілом із трьох, Борис двома з трьох, Сергій не промахується ніколи. Вони стріляють по черзі, Аня, Борис, Сергій і знову по колу, доки не лишиться один. Кожен сам обирає, у кого цілитися, і може вистрілити в повітря. У кого найбільше шансів лишитися останнім?
В Ані, якщо свій перший постріл вона пустить у повітря. Борис і Сергій найбільше бояться одне одного і стріляють одне в одного. Хто б із них не вцілів, наступний постріл буде Аниним. Аня лишається останньою з імовірністю 25/63 ≈ 39,7%, Борис 38,1%, а снайпер Сергій лише 22,2%.
Дуель на трьох називають труеллю. Уявіть пейнтбол чи водяні пістолети: у кого влучили, той вибуває з гри. Ось правила.
Аня влучає в ціль з імовірністю 1/3, Борис 2/3, Сергій 1, тобто завжди. Кожен знає влучність інших.
Стріляють по одному пострілу по черзі: Аня, Борис, Сергій, знову Аня і так далі. Хто вибув, той пропускає свої ходи.
На своєму ході стрілець сам обирає ціль: будь-кого з тих, хто ще в грі. Або стріляє в повітря, тобто навмисно ні в кого. Це дозволено. Промах нікому не шкодить.
Гра триває, доки не лишиться один. Кожен хоче, щоб останнім був саме він, і грає найкраще, що може. Інші теж грають найкраще, і всі це знають.
У кого з трьох найбільше шансів лишитися останнім?
«Звісно, в Сергія: він же не промахується»
Саме тому він найнебезпечніший, і Борис стріляє саме в нього. Найкращі шанси в Ані: поки Борис і Сергій зайняті одне одним, у неї ніхто не цілиться.
Усі троє грають найкраще, що можуть. Зафіксуйте відповідь, перш ніж читати далі.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Подивіться очима Сергія, коли Аня й Борис обоє в грі. Кого з них йому вигідніше вибити: після кого він лишиться в легшій дуелі?
Тепер очима Бориса: що з ним станеться, якщо Сергій доживе до свого ходу? Отже, у кого стрілятиме Борис?
Нарешті очима Ані: що буде, якщо вона влучить у Сергія чи в Бориса? А якщо не влучить ні в кого, хто стрілятиме першим у дуелі, що лишиться?
На кожному своєму ході оберіть, у кого стріляти, або стріляйте в повітря. Борис і Сергій грають за найкращою для себе стратегією, а влучання вирішує жереб з їхньою влучністю. Скільки труелей із десяти ви виграєте?
Аня має три варіанти першого пострілу: у повітря, у Бориса чи в Сергія. Для кожного комп'ютер розігрує 100 000 труелей і рахує, хто лишився останнім. Поруч точні ймовірності за формулами з раунду 4. Змінюйте влучність повзунками: Борис і Сергій щоразу обирають свої найкращі цілі заново.
Шанси в труелі вирішує не те, як добре ви стріляєте, а те, наскільки ви небезпечні для інших.
Шар «На пальцях» приховано на всіх задачах.
Почнімо з простого, хоч і неповного пояснення. Подивіться очима Сергія: якщо він виб'є Аню, то лишиться сам на сам із Борисом, і першим стрілятиме Борис. Якщо виб'є Бориса, лишиться з Анею, яка влучає лише раз із трьох. Друге набагато краще, тож Сергій стріляє в Бориса.
Борис знає це. Якщо Сергій лишиться в грі до свого ходу, Борис вибуде напевно. Тож Борис стріляє в Сергія. Поки обидва в грі, в Аню не цілиться ніхто.
Якщо Аня влучить у Бориса, Сергій наступним ходом влучить у неї, і все. Якщо вона влучить у Сергія, то лишиться з Борисом, і першим стрілятиме він: дві третини, що Аня вибуде одразу. А коли Аня стріляє в повітря, Борис і Сергій розбираються між собою, і хто б не вцілів, першою по ньому стрілятиме вона.
Шар «Строго» приховано на всіх задачах.
Разом: 2/7 + 1/9 = 18/63 + 7/63 = 25/63 ≈ 39,7%
Звідки 3/7 у дуелі Ані з Борисом, де Аня стріляє першою? Розгляньмо одне коло з двох пострілів. Аня влучає з імовірністю 1/3, тобто 3/9. Борис отримує свій постріл, якщо Аня промахнулася, і влучає: 2/3 × 2/3 = 4/9. Ще 2/9 обидва мажуть, і коло повторюється з тими самими шансами. Отже, рішучі кола закінчуються на користь Ані й Бориса як 3 до 4, і Аня виграє дуель у 3 випадках із 7.
Борис виграє, якщо влучить у Сергія і потім виграє дуель: 2/3 × 4/7 = 8/21 ≈ 38,1%. Сергій виграє, лише якщо Борис промахнеться, а потім промахнеться Аня: 1/3 × 2/3 = 2/9 ≈ 22,2%. Разом 25/63 + 24/63 + 14/63 = 1.
| Хто | Перший постріл | Шанс вижити |
|---|---|---|
| Аня | у повітря | 25/63 |
| у Сергія | 59/189 | |
| у Бориса | 50/189 | |
| Борис | у Сергія | 8/21 |
| в Аню або в повітря | 0 | |
| Сергій | у Бориса | 2/9 |
| в Аню | 1/9 | |
| у повітря | 0 |
Кожен рядок показує, що станеться, якщо змінить свій вибір лише цей гравець, а двоє інших гратимуть як у виділених рядках. Жодна зміна не допомагає, тож виділена трійка є рівновагою Неша. Ми перебрали всі 27 комбінацій цілей точними дробами: інших рівноваг тут немає.
Перший стрілець влучає з імовірністю p, другий q. Перший виграє першим пострілом, або після двох промахів третім, або після чотирьох п'ятим…
Аня першою проти Бориса і Борис першим проти Ані:
Три перші постріли Ані:
1/7 тут означає шанс Ані в дуелі, де першим стріляє Борис: 1 − 6/7. Промах Ані по Сергію чи Борису веде в ту саму гру, що й постріл у повітря, тому друга частина кожної суми дорівнює 2/3 · 25/63.
Шар «Глибше» приховано на всіх задачах.
Якщо кожен зобов'язаний у когось цілитися, Аня стріляє в Сергія: це найменше зло. Рівновага знову одна, але тепер Аня, влучивши, віддає Борисові перший постріл у дуелі. Уся перевага слабкого трималася на праві нічого не робити.
Наша черга дуже вигідна Ані: вона стріляє першою, а Сергій останнім. Якщо порядок обирає жереб, то в половині випадків Сергій стріляє раніше за Бориса, одразу його вибиває, і Ані лишається один постріл з трьох. Усереднення за шістьма можливими порядками дає Сергієві 4/9. Тож «виживає найслабший» не закон, а наслідок правил.
Так 1954 року назвав свою статтю економіст Мартін Шубік, один із засновників теорії ігор. У ній він і запропонував слово «труель». Його питання було ширшим за стрілянину: якщо кожен грає найкраще для себе, чи мусить перемагати найсильніший? Труель дає відповідь «не обов'язково» на найпростішому прикладі.
1975 року канадський математик Марк Кілґур у статті «The Sequential Truel» розібрав послідовну труель, де стріляють по черзі, як у нашій задачі. 1997 року він разом зі Стівеном Брамсом підсумував відомі варіанти в оглядовій статті «The Truel» у Mathematics Magazine. Ми перевірили наші числа незалежно: точними дробами в Python і симуляцією.
Математично можна подивитися, за яких влучностей перевага першої стрільчині зберігається. Логічно це історія про лідера, у якого цілиться кожен. А на практиці це питання, яке варто ставити в будь-якому змаганні трьох: кого найбільше бояться мої суперники?
Математика
По горизонталі влучність Ані, по вертикалі Бориса. У кожній точці сторінка перебирає всі 27 комбінацій цілей, знаходить рівновагу Неша і фарбує точку в колір того, у кого найбільше шансів. Черга та сама: Аня, Борис, Сергій. Клацніть по карті, щоб побачити точні шанси й ходи.
Над діагоналлю Аня стріляє гірше за Бориса. Що ширша там рожева зона, то частіше найслабша перемагає. Зменште влучність Сергія: він перестає бути таким страшним для Бориса, і картина змінюється.
Логіка
Тут n гравців із влучністю 1/n, 2/n, …, 1. Стріляють по черзі від найслабшого до найсильнішого за простим правилом: кожен цілиться в найвлучнішого з тих, хто ще в грі. Це не доведена рівновага для n > 3, а модель коаліції проти лідера, порахована точно.
Логіка та сама, що в труелі: найсильніший небезпечний для всіх, тож усі мовчки об'єднуються проти нього, навіть не домовляючись. Він стріляє останнім і часто не доживає до свого ходу. Шанси отримують ті, на кого ніхто не дивиться. Фізики Пау Аменгуаль і Рауль Тораль 2006 року теж відзначили, що зі зростанням кількості гравців шанс найкращого стрільця падає.
Практика
Перевірте себе на класиці. Мартін Ґарднер пропонував читачам «трикутну дуель»: Сміт влучає завжди, Браун у 80% пострілів, Джонс у 50%, а чергу визначає жереб. Натисніть «Ґарднер»: Джонс, найгірший стрілець, виживає з імовірністю 47/90 ≈ 52,2%, Сміт 3/10, Браун лише 8/45.
У житті ніхто нікого не вибиває одним пострілом, і модель тут дає не прогноз, а питання. На виборах із трьома кандидатами двоє лідерів, що атакують одне одного, можуть звільнити місце третьому. На ринку з трьома компаніями цінова війна двох великих може бути вигідною меншій. Але чи так буде, залежить від правил, як і в труелі: хто ходить першим, чи можна відмовчатися, чи вибуває переможений насправді.
У романі Фредеріка Марріета «Мічман Ізі» є дуель утрьох, де кожен учасник цілиться лише в одного визначеного суперника. Обирати ціль, як у нашій задачі, там не можна.
Дослідники труелей зазвичай називають першою появою задачі «Енциклопедію головоломок і розваг» Кларка Кіннерда (Encyclopedia of Puzzles and Pastimes, 1946). Згодом задачу часто подають м'якше: учасники стріляють не одне в одного, а по повітряних кульках суперників.
Мартін Шубік склав слово truel з three і duel у статті «Does the Fittest Necessarily Survive?» у збірці «Readings in Game Theory and Political Behavior».
У версії Мартіна Ґарднера Сміт влучає завжди, Браун у 80%, Джонс у 50%, а чергу тягнуть жеребом. Джонс, найгірший стрілець, виживає частіше за всіх: 47/90. Ми перерахували це число в розділі «Практика».
Фінальну сцену фільму Серджо Леоне «Хороший, поганий, злий» часто називають труеллю: троє стоять колом на кладовищі. Але це не наша задача: там стріляють одночасно, а результат вирішено заздалегідь, бо Блонді потай розрядив револьвер Туко.
Пау Аменгуаль і Рауль Тораль назвали свій огляд «Truels, or the survival of the weakest». Вони розібрали випадкові й послідовні труелі, «ліги» труелей і ігри на мережах.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.