Верный способ войти в историю – ответить, кто побеждает в шахматах при идеальной игре обеих сторон (белые, чёрные или дружба). Нужны ли гроссмейстеры и суперкомпьютеры, чтобы узнать истину? Или достаточно карандаша, бумаги и красивой идеи?
Математика вселяет надежду, ведь можно доказать существование объекта, не предъявляя его, найти ответ, не разъясняя глубинные причины, почему он именно такой.
В задаче про заключённых и сто коробок схожая ситуация. Колоссальное количество возможных стратегий игры, одна из которых интуитивно показалась нам наилучшей. Но можно ли обосновать её оптимальность, не погружаясь в месиво вариантов?
В самом посте о задаче такого вопроса не поставлено. Однако уже в первом комментарии к нему пользователь 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-ти коробок. Однако для дальнейших рассуждений оказывается выгоднее позволить игрокам вскрывать любое количество ящиков, даже если заведомо понятно, что они проиграли.
Введённая нами новая игра обладает тремя интересными свойствами, которые будут рассмотрены далее и позволят дать обоснованный ответ – обеспечивает ли базовая стратегия максимальную вероятность победы или нет.
Справедливо кажется, что так как коробки не закрываются, то в новую игру команде легче победить, чем в исходную.
Действительно, какой бы стратегии прохождения первоначального испытания ни придерживались участники, они могут адаптировать её и для прохождения нового.
Для этого тем игрокам, которые не обнаружили номера в открытых коробках, надо вскрывать ящики так, как они делали бы это в процессе исходной игры. При этом если стратегия указывает им открыть уже вскрытый ящик, они просто экономят попытку.
Ясно, что для одного и того же расположения номеров по коробкам, если игроки побеждают в первую игру, то они победят и во вторую. Таким образом, максимальная вероятность успешного прохождения исходного испытания не может быть больше, чем нового.
Другими словами, если бы максимальная вероятность победы в первую игру была, скажем, 40%, то и новое испытание можно было бы успешно проходить с такими же или большими шансами – назовём это свойством 1.
Если подумать, то первому игроку не важно, какой стратегии придерживаться – как бы он ни старался, вероятность найти свой номер, уложившись при этом в лимит по количеству попыток, составит 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 доказано.
Вернёмся к исходной игре. Вспомним, что вероятность победы в неё при использовании базовой стратегии (той самой, при которой игроку надо начинать поиски с коробки с его собственным номером, а далее руководствоваться числами на найденных жетонах) равна <количество перестановок чисел от 1 до 6, не содержащих циклы длины более 3>/6! (как и прежде предполагается, что коробок и игроков по шесть, а попыток три).
Если обозначить B – множество перестановок чисел от 1 до 6, не содержащих циклы длины более 3, а |B|, соответственно, число таких перестановок, то описанная выше формула примет вид |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, ..., 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» выглядит так:
При необходимости задать ход 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 попытки, участники могут действовать следующим образом.
Стратегия первого игрока описывается строкой таблицы:
Стратегия второго игрока описывается строкой таблицы:
В этом случае команда будет побеждать с вероятностью 10/24 (на 10 из 4! = 24 возможных вариантах расположения жетонов по коробкам), точно также, как и в случае использования базовой стратегии.
С учётом сложившегося понимания игры можно предположить, что максимальная вероятность победы в случае n коробок, m игроков и k попыток вычисляется по формуле:
<число перестановок, в которых элементы 1, 2, …, m не входят в циклы длины больше k>/n!
В простейших случаях, например, при n = m, k ≥ n/2 она доказана и выглядит довольно красиво: 1 – 1/(k+1) – 1/(k+2) – … – 1/n.
Формальное доказательство формулы и её вывод в явном виде для различных значений параметров представляет собой интересную проблему. Буду благодарен за ссылки на статьи, где число интересующих перестановок подсчитано или решены аналогичные комбинаторные задачи.
Математика вселяет надежду, ведь можно доказать существование объекта, не предъявляя его, найти ответ, не разъясняя глубинные причины, почему он именно такой.
В задаче про заключённых и сто коробок схожая ситуация. Колоссальное количество возможных стратегий игры, одна из которых интуитивно показалась нам наилучшей. Но можно ли обосновать её оптимальность, не погружаясь в месиво вариантов?
В самом посте о задаче такого вопроса не поставлено. Однако уже в первом комментарии к нему пользователь 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!).
Если бы игроки, применяя базовую стратегию, не прекращали движения, найдя свой жетон, то они стали бы ходить по кругу. Например, первый участник, заглянув в первую коробку, двинулся бы ко второй, затем в пятую, оттуда снова в первую и т.д. Между этими же номерами ходили бы второй и пятый игроки. Третий участник открывал бы всё время третью коробку, а четвертый и шестой метались бы между четвертым и шестым ящиками.
Это и означает, по сути, что перестановка (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, k ≥ n/2 она доказана и выглядит довольно красиво: 1 – 1/(k+1) – 1/(k+2) – … – 1/n.
Формальное доказательство формулы и её вывод в явном виде для различных значений параметров представляет собой интересную проблему. Буду благодарен за ссылки на статьи, где число интересующих перестановок подсчитано или решены аналогичные комбинаторные задачи.