Задача про ста коробках і порятунку ув'язнених – фінальний акорд

Вірний спосіб увійти в історію – відповісти, хто перемагає в шахах при ідеальній грі обох сторін (білі, чорні або дружба). Потрібні гросмейстери і суперкомп'ютери, щоб дізнатися істину? Чи достатньо олівця, паперу і красивої ідеї?

Математика вселяє надію, адже можна довести існування об'єкта, не пред'являючи його, знайти відповідь, не пояснюючи глибинні причини, чому він саме такий.

У задачі про ув'язнених і сто коробок схожа ситуація. Колосальна кількість можливих стратегій гри, одна з яких інтуїтивно здалася нам найкращою. Але можна обґрунтувати її оптимальність, не занурюючись в місиво варіантів?

У самому пості про завдання такого питання не поставлено. Однак вже в першому коментарі до нього користувач mayorovp піднімає тему, а трохи нижче avfonarev повідомляє про чудову статті, розкриває таємницю.

Цим варто перейнятися, тим більше що міркування прості і витончені. В цілому ж основна ідея посту не в рішенні конкретної задачі (що само по собі теж цікаво), а скоріше в тому, щоб в черговий раз дати привід здивуватися могутності або, як висловився Вігнера, незбагненною ефективності математики.

Коротко про умови та вирішенні задачі

Нагадаю, що сто гравців повинні знайти жетони зі своїми номерами, розкладені по сто коробок. Кожен може заглянути не більш ніж половину з них в будь-якому угодном йому порядку. У процесі випробування всі коробки і жетони залишаються на місці, гравці не зустрічаються і ніяким іншим способом не можуть обмінюватися інформацією, коробки, після того як у них завітали, знову закриваються. Команда перемагає, тільки якщо всім учасникам вдається знайти свій номер.

Якщо гравці будуть відкривати коробки навмання, то ймовірність перемоги складе (50/100)100, тобто близько 10-29%. Однак варто їм попередньо домовитися і (увага, спойлер!) шанси на виграш стають майже 31,2%!

Для цього слід використовувати наступну стратегію – кожному учаснику потрібно починати пошуки з коробки, яка має його власний номер, а потім відкривати ящики з номером щойно виявленого жетона.

Щоб згадати детальніше можна почитати вихідний пост про завдання або подивитися полутораминутное відеоSolution to The Impossible Bet», про який розповів andreymironov.

Нам же хочеться зрозуміти, чому не можна (або можна) вигравати частіше, ніж у 31,2% випадків.

Обхідний маневр – розглянемо нову гру

Описана вище стратегія (назвемо її базової) – це один з близько 100100 * 99100*99 *… * 51100*99*...*51 можливих варіантів дій гравців (див. розділ «Підрахунок числа стратегій»). Тому просто порівняти в лоб базову стратегію з усіма іншими не вийде.

У статті «The Locker Puzzle» пропонується для початку вивчити іншу гру (назвемо її новій або другий), в якій коробки назад не закриваються, а гравці шукають свої номери без обмежень на кількість спроб. Точні правила такі:

— гравці проходять випробування по черзі – спочатку перший, потім другий, третій і т. д.;

— перший гравець повинен відкривати ящики до тих пір, поки не знайде свій номер, скільки б спроб не знадобилося. Відкриті ним коробки не закриваються;

— другий, третій і далі гравці, насамперед, намагаються виявити свій номер во всіх відкритих коробках (зазирнути у відкриту коробку не вважається спробою). Якщо (і тільки якщо) це не принесло успіху, їм слід розкривати закриті ящики до тих пір, поки не знайдеться потрібний жетон. Відкриті ними коробки також не закриваються;

— команда перемагає, тільки якщо жоден з учасників не знадобилося понад 50-ти спроб на те, щоб відшукати свій номер, тобто якщо нікому не довелося розкрити більше половини від загального числа ящиків.

Так як коробки не закриваються, то чим більше їх відкрито, тим легше гравцям перемогти. Наприклад, якщо першому учаснику довелося розкрити 35 ящиків, то ще 34 гравцям шукати номери взагалі не доведеться, а іншим залишиться всього 65 варіантів, де може знаходитися їх жетон.

Крім того, якщо якийсь гравець в пошуках свого номера відкриє ще, скажімо, 20 ящиків, то команда вже зовсім не зможе програти, так як залишиться всього 100 – 35 – 20 = 45 невідкритих коробок, і витратити більше 50-ти спроб стане неможливо.

Вельми цікаво сформульована умова перемоги. Здавалося б, можна просто переривати гру, якщо хтось відкрив понад 50-ти коробок. Однак для подальших міркувань виявляється вигідніше дозволити гравцям розкривати будь-яку кількість ящиків, навіть якщо свідомо зрозуміло, що вони програли.

Вихідну гру, до речі, також можна переформулювати з урахуванням цієї ідеї.Кожен гравець шукає свій номер до тих пір, поки не знайде, навіть якщо знадобиться понад 50-ти спроб. Тим не менш, команда перемагає, тільки якщо ніхто не перевищив цього ліміту, тобто не відкрив в процесі пошуків більше половини від загального числа коробок. Максимальна ймовірність перемоги від такого коригування правил не зміниться.
Введена нами нова гра володіє трьома цікавими властивостями, які будуть розглянуті далі і дозволять дати обгрунтовану відповідь – забезпечує базова стратегія максимальну ймовірність перемоги чи ні.

Властивість 1 – в нову гру виграти легше

Справедливо здається, що так як коробки не закриваються, то в нову гру команді легше перемогти, ніж у вихідну.

Дійсно, який би стратегії проходження початкового випробування дотримувалися учасники, вони можуть адаптувати її для проходження нового.

Для цього тим гравцям, які не виявили номери у відкритих коробках, треба розкривати ящики так, як вони робили б це в процесі вихідної гри. При цьому якщо стратегія вказує їм відкрити вже розкритий ящик, вони просто економлять спробу.

Ясно, що для одного і того ж розташування номерів по коробках, якщо гравці перемагають у першу гру, то вони переможуть і в другу. Таким чином, максимальна ймовірність успішного проходження вихідного випробування не може бути більше, ніж нового.

Іншими словами, якби максимальна ймовірність перемоги в першу гру була, скажімо, 40%, то і нове випробування можна було б успішно проходити з такими ж або великими шансами – назвемо це властивістю 1.

Властивість 2 – в новій грі від стратегії команди нічого не залежить

Якщо подумати, то першому гравцеві не важливо, якої стратегії дотримуватися – як би він не старався, ймовірність знайти свій номер, вклавшись при цьому в ліміт по кількості спроб, складе 50/100 = ½. Не залежить від обраного алгоритму і те, скільки саме коробок він відкриє – одну, дві, тридцять чи всі сто.

Гравці, жетони яких вже знайдено попередніми учасниками, за умовами гри знаходять свій номер стовідсотково і за нуль спроб – в їх алгоритмі дій нічого не можна поліпшити.

Ті ж члени команди, які змушені самі шукати свої номери, знаходяться, по суті, в такій же ситуації, як і перший гравець – шанси на успіх залежать від кількості закритих ящиків, а не від вмісту вже розкритих або обраної ними стратегії.

Виникає відчуття, що ймовірність перемоги в нову гру не залежить від алгоритму дій команди. Назвемо це властивістю 2 і обґрунтуємо більш формально.

Для зручності припустимо, що коробок і гравців у нас по шість, а спроб три.

Уявімо, що учасники почали проходження випробування за новими правилами, а ми хочемо законспектувати їх успіхи. Виявляється, процес гри можна досить докладно описати лише одним рядком чисел, вказавши номери виявлених командою жетонів в тому порядку, в якому їх знаходили.

Наприклад, легко розшифрувати запис(2, 5, 1, 3, 6, 4). Адже за умовою гри перший гравець повинен був розкривати ящики до тих пір, поки не знайде 1. Тому можна однозначно відновити, що перший учасник, відкривши три якісь (не важливо) коробки, виявив там номери 2, 5 і 1. Другого думати не довелося, його жетон виявився вже в розкритому першим гравцем ящику. Потім третій домігся успіху з першої спроби і, нарешті, четвертий виявив 6 і 4. П'ятого та шостого учасникам, також як другого, працювати не знадобилося.

Інший приклад – припустимо, що результати проходження випробування описуються рядком(6, 1, 5, 3, 4, 2). Легко бачити, що перший учасник знайшов свій жетон вже у друге за рахунком відкритій коробці, тоді як другого гравцеві не пощастило, знадобилося чотири спроби, тому команді зараховано поразку.

Виходить, що рядок з шести чисел, які відповідають номерам знайдених гравцями жетонів, однозначно визначає результат випробування – перемогла команда чи програла.

До слова, рядки типу(2, 5, 1, 3, 6, 4) і(6, 1, 5, 3, 4, 2), тобто такі які містять числа від 1 до 6 без повторень, називаються перестановками чисел від 1 до 6. Відомо, що всього таких перестановок 6! = 6*5*4*3*2*1.

Зауважимо, що так як жетони розкладені по коробках випадково, то в кожному з ящиків з рівними шансами може виявитися будь-який з шести номерів. Тому, будь-якого алгоритму ні дотримувався перший гравець (навіть якщо він робить вибір навмання), в перший відкритої їм коробці з рівною ймовірністю 1/6 може виявитися будь-який з шести номерів.

У другій відкритою командою коробці (не важливо, ким першим або другим учасником – і у відповідності з якими міркуваннями) з однаковою ймовірністю 1/5 може виявитися будь-який з п'яти залишилися номерів.

Продовжуючи міркування, прийдемо до того, що, записуючи номери жетонів в тому порядку, в якому їх знаходили, можна з однаковою ймовірністю(1/6)*(1/5)*...(1/2)*(1/1) = 1/6! отримати будь-яку з 6! можливих перестановок чисел від 1 до 6.

Як показано вище, одні перестановки, наприклад, (2, 5, 1, 3, 6, 4), свідчать про виграші гравців, інші, зокрема, (6, 1, 5, 3, 4, 2) – про програші. Позначимо A – безліч всіх перестановок, що означають перемогу команди, а |A|, відповідно, кількість таких перестановок.

Так як всі перестановки можуть вийти в результаті гри рівноймовірно, то шанси на перемогу гравців рівні |A|/6! і, як видно, не залежать від обраної ними стратегії. Властивість 2 доведено.

Властивість 3 – ймовірність перемоги при використанні базової стратегії дорівнює шансів на виграш в нову гру

Повернемося до вихідної грі. Згадаймо, що ймовірність перемоги в неї при використанні базової стратегії (тієї самої, при якій гравцеві треба починати пошуки з коробки з його власним номером, а далі керуватися числами на знайдених жетонах) дорівнює <кількість перестановок чисел від 1 до 6, що не містять цикли довжини понад 3>/6! (як і раніше передбачається, що коробок і гравців по шість, а спроб три).

Якщо позначити B – множина перестановок чисел від 1 до 6, що не містять цикли довжини понад 3, а |B|, відповідно, кількість таких перестановок, то описана вище формула прийме вид |B|/6!

Про циклах і про те, як виходить ця формула...Припустимо, що розташування жетонів по коробках описується перестановкою(2, 5, 3, 6, 1, 4), тобто у першій коробці лежить 2-ка, у другій – 5-ка, в третій – 3-ка і т. д.

Якщо б гравці, застосовуючи базову стратегію, не припиняли руху, знайшовши свій жетон, то вони стали ходити по колу. Наприклад, перший учасник, заглянувши в першу коробку, рушив би до другої, потім в п'яту, звідти знову в першу і т. д. Між цими ж номерами ходили б другий і п'ятий гравці. Третій учасник відкривав би весь час третю коробку, а четвертий і шостий металися між четвертим і шостим ящиками.

Це й означає, по суті, що перестановка(2, 5, 3, 6, 1, 4) розбивається на цикли [1, 2, 5], [3], [4, 6].

Причому один і той же цикл можна визначити кількома способами, скажімо, [1, 2, 5] = [5, 1, 2] = [2, 5, 1], тобто в запису допускається циклічний зсув.

Кажуть також, що перестановка представляється у вигляді твори непересічних циклів: (2, 5, 3, 6, 1, 4) = [1, 2, 5] [3] [4, 6]. Таке уявлення не єдино, так як вище зазначено, що цикли можуть бути записані по-різному, крім того, їх можна переставити між собою, зокрема, (2, 5, 3, 6, 1, 4) = [1, 2, 5] [3] [4, 6] = [3] [1, 2, 5] [4, 6] = [3] [5, 1, 2] [6, 4] і так далі.

Однак якщо зафіксувати спосіб запису циклів (наприклад, використовувати тільки ту запис, при якій мінімальний елемент розташований на останньому місці: [1, 2, 5] або [5, 1, 2], а саме [2, 5, 1]) і зафіксувати також порядок проходження циклів (наприклад, у порядку зростання мінімальних елементів (позначені жирним): не [6, 4] [3] [2, 5, 1], а [2, 5, 1] [3] [6, 4]), то тоді уявлення перестановки у вигляді добутку непересічних циклів буде єдиним. Наприклад: (2, 5, 3, 6, 1, 4) = [2, 5, 1] [3] [6, 4].

Базова стратегія принесе гравцям виграш, тільки якщо нікому не доведеться бігати більше ніж між трьома коробками, іншими словами, тільки якщо всі цикли мають довжину 3 або менше. Звідси ймовірність перемоги: <число перестановок, не містять циклів довжини більше 3> (тобто |B|), поділена на загальну кількість перестановок (6!).
Згадаємо також тільки що проведені у попередньому розділі міркування, згідно з якими максимальна (і єдино можлива) ймовірність перемоги в нову гру обчислюється за формулою <число перестановок, що означають перемогу гравців>/<загальне число перестановок> або |A|/6! у наших позначеннях.

Звернемо увагу, що входять до множини A B перестановки чимось схожі. І ті й інші, зокрема, розбиваються на шматки», що містять не більше 3 чисел.

Так, перестановку(2, 5, 1, 3, 6, 4) з A можна умовно розділити на три частини <2, 5, 1> <3> <6, 4> за принципом, що в кожну частину входять тільки ті номери, які відкриті одним гравцем (<2, 5, 1> виявлені першим учасником, <3> – третім, <6, 4> – четвертим).

Відмінною особливістю таких «шматків» є те, що мінімальний елемент у них завжди знаходиться на останньому місці, а самі «шматки» розташовані в порядку зростання мінімальних елементів. Підкреслимо це, виділивши мінімальні елементи жирним: <2, 5, 1> <3> <6, 4>.

У свою чергу перестановку з B, скажімо, (2, 5, 3, 6, 1, 4), можна уявити у вигляді добутку непересічних циклів: (2, 5, 3, 6, 1, 4) = [1, 2, 5] [3] [4, 6] = [3] [1, 2, 5] [4, 6] = [3] [5, 1, 2] [6, 4] =…

З усіх можливих варіантів такого подання виберемо той єдиний, при якому мінімальні елементи циклів розташовані на останньому місці, а самі цикли розставлені в порядку зростання їх мінімальних елементів, тобто(2, 5, 3, 6, 1, 4) = [2, 5, 1] [3] [6, 4].

Виходить, що перестановка(2, 5, 3, 6, 1, 4) з B умовно розбивається на «шматки» <2, 5, 1> <3> <6, 4>, рівно ті ж, що і перестановка(2, 5, 1, 3, 6, 4) з A. Це підказує нам алгоритм, що дозволяє перетворити будь-яку перестановку з A перестановку з B і навпаки.

Дійсно, візьмемо перестановку(2, 5, 1, 3, 6, 4) з A, розіб'ємо її обумовленим вище способом на «шматки» <2, 5, 1> <3> <6, 4>, замінимо в цьому записі кутові дужки на квадратні, а коми – на знак множення циклів (у нашому випадку на пробіл) і отримаємо [2, 5, 1] [3] [6, 4] = (2, 5, 3, 6, 1, 4) з B.

В зворотний бік також: (2, 5, 3, 6, 1, 4) з B подамо у вигляді [2, 5, 1] [3] [6, 4], поміняємо дужки, додамо коми і «склеим» отримані шматки <2, 5, 1> <3> <6, 4> у перестановку(2, 5, 1, 3, 6, 4) з A.

Ось інший приклад взаємного перетворення: (6, 1, 4, 2, 3, 5) з A <-> <6, 1> <4, 2> <3> <5> <-> [6, 1] [4, 2] [3] [5] = (6, 4, 3, 2, 5, 1) з B.

Таким чином, елементи множин A B розбиті на пари перетворюються один в одного за вказаною вище алгоритмом перестановок. На мові математики це означає, що між множинами A B побудована биекция, отже, у них однакову кількість елементів, тобто |A| = |B|.

Значить, шанси на успішне проходження вихідного випробування при використанні базової стратегії (|B|/6!) ймовірність перемоги в нову гру (|A|/6!) рівні. Назвемо це властивістю 3.

Висновки – оптимальність базової стратегії

Для наочності властивості 1, 2 і 3 доведені на прикладі гри з шістьма коробками, шістьма гравцями і трьома спробами. Зрозуміло, що точно такі ж міркування можна повторити і в загальному випадку, коли коробок і гравців n (наприклад, за 100), а спроб k (наприклад, 50).

З розглянутих властивостей випливають два твердження:

1) Ймовірність перемоги в нову гру не залежить від стратегії команди (властивість 2) і в точності дорівнює шансів на успішне проходження вихідного випробування при використанні базової стратегії (властивість 3).

2) Базова стратегія забезпечує максимальну ймовірність перемоги команди у вихідну гру, так як якщо б яка-небудь інша стратегія забезпечувала б велику ймовірність перемоги, то з великими шансами на успіх можна було б проходити і нове випробування (властивість 1), що суперечить твердженням 1) вище.

Таким чином, якщо кожен гравець будуть починати пошуки з коробки, яка має його власний номер, а потім відкривати ящики з номером щойно виявленого жетона, то команда буде перемагати з максимально можливою ймовірністю. Нічого учасникам краще не придумати. Тепер це не тільки інтуїтивне пропозицію, але і доведений факт!

Тільки вдумайтеся, колосальна кількість можливих стратегій гри просто залишилися осторонь – ми відповіли на питання про оптимальність однієї з них, так і не зрозумівши, в чому ж її принципова відмінність від інших!

Нам навіть не знадобилося обчислювати цю саму ймовірність перемоги, максимальне якої ми довели! Не довелося розглядати і такі питання по суті завдання, як: що таке стратегія і скільки їх? є базова стратегія єдиною оптимальною чи є ще й інші? за якою формулою обчислюється максимальна ймовірність перемоги у разі n коробок, m гравців і k спроб?

Ось чому я написав на самому початку, що математика вселяє надію – адже можна увійти в історію просто напросто довівши, наприклад, що в шахах при ідеальній грі обох сторін завжди буде нічия або перемога білих або чорних (це було б взагалі приголомшливо – показати, що білі з самого першого ходу в цугцвангу!). Не виключено, що завдяки «незбагненною ефективності» математика, її дивовижної здатності красиво і точно відповідати на поставлені питання, для цього зовсім не потрібно проникати вглиб шахової теорії або задіяти величезні обчислювальні потужності.

Вперед до нових вершин! Для тих же, кому цікаво глибше розібратися із завданням про сто коробок і порятунок ув'язнених, припасені бонусні голови.

Бонус. Підрахунок числа стратегій

Алгоритм дій команди (назвемо це колективної стратегією гравців) складається з алгоритмів дій кожного гравця окремо (назвемо їх індивідуальними стратегіями гравців).

Будемо вважати, що учасники вибирають номер черговий коробки, яку вони відкриють, однозначно, виходячи з передісторії, тобто не використовують випадкового механізму (не можуть, наприклад, обирати будь-яку з решти коробок випадково).

Тоді індивідуальна стратегія, скажімо, першого гравця може бути описана рядком у таблиці такого вигляду:

Хід 1 Хід 2 Хід 3
2 3 ... n ...
У перший стовпець («Хід 1») записується номер коробки, з якої перший гравець починає пошук. У колонках 2, 3, ..., n (під загальною шапкою «Хід 2») записується номер коробки, яку він буде відкривати, якщо в першому розкритому їм ящику виявиться жетон з номером 2, 3, ..., n відповідно. Для завдання ходу 2 вимагається n — 1 число (не n, так як стовпця з ім'ям 1 немає, адже якщо учасник на час знайшов 1 жетон з номером 1 (тобто свій жетон), то продовжувати пошук нема чого).

У стовпці під загальною шапкою «Хід 3» записуються номери третин коробки, в якій гравець буде шукати свій жетон, в залежності від того, які номери він виявив у перших двох розкритих ящиках. Для завдання ходу 3 потрібно вказати вже (n — 1)*(n — 2) чисел (на час 1 може бути виявлений один з n — 1 номерів, а на час 2: n — 2, так як номер, виявлений на ході 1, вже не попадеться).

Шапка для «Хід 3» виглядає так:
Хід 3
2 3 ... n
3 4 ... n ... ... ...
При необхідності задати хід k потрібно (n – 1) * (n – 2) *… * (n k + 1) стовпців.

Підрахуємо, скількома способами можна заповнити рядок такої таблиці.

У перший стовпець можна записати будь-який з n номерів. Стовпці для другої спроби можна заповнити (n – 1)n – 1 способами, так як в кожну з (n – 1) клітинок можна вписати будь-ізn – 1) номерів ще не відкритих коробок.

Варіантів заповнення стовпців для третьої спроби (n – 2)(n – 1) * (n – 2), зважаючи на те, що в кожну з (n – 1) * (n – 2) клітинок можна підставити будь-який ізn – 2) номерів ще не відкритих коробок, і т. д.

Стовпці, відповідні k-ой спробі, можуть бути заповнені (n k + 1)(n – 1) * (n – 2) *… * (n k + 1) способами.

В результаті, існує n * (n – 1)n – 1 * (n – 2)(n – 1) * (n – 2) *… * (n k + 1)(n – 1) * (n – 2) *… * (n k + 1) індивідуальних стратегій першого гравця. Зрозуміло, що у будь-якого іншого гравця кількість стратегій таке ж.

Гравці діють незалежно один від одного. Колективна стратегія являє собою комбінацію індивідуальних стратегій, тому їх загальна кількість виходить перемножуванням числа індивідуальних стратегій кожного з гравців:
n * (n – 1)n – 1 * (n – 2)(n – 1) * (n – 2) *… * (n k + 1)(n – 1) * (n – 2) *… * (n k + 1) в ступені n дорівнює nn * (n – 1)n * (n – 1) * (n – 2)n * (n – 1) * (n – 2) *… * (n k + 1)n * (n – 1) * (n – 2) *… * (n k + 1).

Якщо гравців не стільки ж, скільки коробок, то зводити треба не в ступінь n, а ступінь m, m – кількість гравців.

Бонус. Єдиність оптимальної стратегії

Цікаве питання – чи є базова стратегія єдиною оптимальною? Чи можуть, наприклад, гравці починати пошуки не з коробки з їх власним номером, а з якою-небудь інший?

Уявімо, що перед самим початком випробування коробки перенумеровали. Зрозуміло, що це ніяк не вплине ні на стратегії гравців, ні на ймовірність перемоги. Адже перенумерувати коробки – це все одно як перекласти жетони, але ми вважаємо, що вони розкладені випадково.

Гравці можуть і самі подумки перенумерувати ящики. Наприклад, п'яту вважати коробку сьомий, сьому – десяту, а десяту – п'ятою. У цьому випадку, використовуючи принцип все тієї ж базової стратегії, скажімо, п'ятий гравець буде починати пошуки з сьомого скриньки і якщо виявить у процесі випробування 7-ку, піде заглядати в десятий, а знайшовши 10-ку – у п'ятий.

Якщо всі гравці однаково подумки перенумеруют коробки, то ймовірність перемоги команди залишиться точно такий же. Поряд з міркуваннями вище, можна навести і формальне, чисто технічне доказ цього факту (думаю, це не настільки цікаво, щоб переписувати його в цьому пості).

У підсумку, так як пронумерувати n скриньок n! способами, то і оптимальних стратегій як мінімум n!, однак, по суті, все це варіації одного і того ж алгоритму дій. Швидше за все, якщо гравців стільки ж скільки і коробок, інших оптимальних стратегій, по-справжньому відрізняються від базової, немає. Докази цього факту ми з товаришем поки не відшукали.

У разі ж якщо гравців менше, ніж коробок, то можливі й інші оптимальні стратегії, які дійсно відрізняються від базової. Наприклад, якщо у нас 4 коробки, 2 гравця і по 2 спроби, учасники можуть діяти наступним чином.

Стратегія першого гравця описується рядком таблиці:
Хід 1 Хід 2
2 3 4
1 2 3 3
Стратегія другого гравця описується рядком таблиці:
Хід 1 Хід 2
1 3 4
2 1 4 4
У цьому випадку команда буде перемагати з імовірністю 10/24 (на 10 4! = 24 можливих варіантах розташування жетонів по коробках), точно також, як і у випадку використання базової стратегії.

Про рішення в загальному випадку

З урахуванням сформованого розуміння гри можна припустити, що максимальна ймовірність перемоги у разі n коробок, m гравців і k спроб обчислюється за формулою:
<число перестановок, в яких елементи 1, 2, ..., m не входять в цикли довжини більше k>/n!

У найпростіших випадках, наприклад, при n = m, kn/2 вона доведена і виглядає досить красиво: 1 – 1/(k+1) – 1/(k+2) –… – 1/n.

Формальне доведення формули та її висновок в явному вигляді для різних значень параметрів являє собою цікаву проблему. Буду вдячний за посилання на статті, де кількість вакансій перестановок підраховано або вирішені аналогічні комбінаторні задачі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.