Выживут ли мудрецы: задача по теории вероятностей, у которой нет единственного правильного решения

Андрей Ковальков

стажёр инженер-тестировщик в Bercut

Злой Дух поймал двух мудрецов и посадил их в разные комнаты своего страшного дома. Затем злой дух подбросил симметричную монету бесконечное количество раз. Все результаты чётных бросков он сообщил одному мудрецу, а все результаты нечётных — второму мудрецу.

После этого Дух предложил каждому мудрецу назвать номер броска из серии другого мудреца. Мудрецу, которому известны результаты чётных бросков, нужно назвать номер любого нечётного броска. Мудрецу, которому известны результаты нечётных бросков, нужно назвать номер любого чётного броска.

Если результаты бросков, названные мудрецами, одинаковые, то Злой Дух подарит мудрецам свободу. Если же результаты отличаются, то казнит их.

Оба мудреца знают о повадках Злого Духа и могли заранее договориться о стратегии.

Какую стратегию им выбрать, чтобы вероятность спасения была больше 50%?

У этой задачи есть много интерпретаций в интернете: мудрецы, принцессы, путешественники, но не в этом суть. Первое, что вызывает интерес, это отсутствие единственного правильного решения. А второе — то, что многие (включая меня), когда первый раз видят эту задачу, неверно понимают условия. Эта задача по теории вероятности, но часто воспринимается как обычная задача на логику. Многие думают, что при озвучивании ответов мудрецы слышат друг друга. Если вы из условий это поняли, вы — молодец! Но я всё равно рассмотрю оба варианта. ?

Вариант 1. Мудрецы слышат друг друга

Да, условия задачи этого не предусматривают, но явным образом также не говорится об обратном. Так почему бы не рассмотреть и такой вариант? Ведь при этом мы с можем вероятностью 100% сохранить жизни нашим мудрецам, мы ведь не желаем им зла.

Для начала представим, что у нас есть бесконечная последовательность бросков. Вот пример начала такой последовательности:

Мы понимаем, что в ответе один из мудрецов должен каким-то образом закодировать и передать второму мудрецу информацию о последовательности результатов, которые ему известны. То есть мы должны придумать такую стратегию, в которой первый мудрец, называя цифру неизвестного ему броска второго мудреца, одновременно сообщал ему о том, какой результат броска нужно искать.

Перед нами симметричная монета, а значит, вероятность выпадения орла и решки всегда 50/50 и не зависит от числа подбрасываний. При этом мы подбрасываем её бесконечно много раз. Значит, по закону больших чисел, фактическое среднее будет стремиться к теоретическому, то есть мы получим примерно в 50% бросков орла и в 50% — решку. Случаи, когда выпадают только орлы или только решки, мы рассматривать не будем, как варианты с очень низкой вероятностью.

Таким образом, наши мудрецы должны договориться о формате сообщения, о каком-то паттерне, который они будут искать в последовательности своих бросков. Один из вариантов такого паттерна: последовательное выпадение орла и решки у первого мудреца.

Алгоритм действий будет следующим:

1. Первый мудрец находит в известной ему последовательности идущие подряд броски, в которых выпал сначала орёл, потом решка.
2. Первый мудрец называет Злому Духу (и второму мудрецу) порядковый номер первого из этих двух бросков. Здесь речь идёт не о чётном или нечётном номере броска в общей серии, а о его порядковом номере у конкретного мудреца. Например, бросок с чётным номером 4 у первого мудреца будет иметь порядковый номер 2. У второго мудреца бросок с порядковым номером 2 будет третьим в общей серии бросков.
3. Второй мудрец проверяет в своей последовательности бросок под названным порядковым номером. Он понимает, что у первого мудреца под этим же номером значится результат броска орёл, а под следующим — решка.
4. Если у первого мудреца под этим номером тоже орёл, то он смело повторяет тот же номер Злому Духу. Если решка, то для того, чтобы результаты у обоих мудрецов совпали, увеличивает номер, который он сообщит Злому Духу, на единицу.

В примере, который приведён в таблице выше, действия мудрецов будут следующими:

1. Первый мудрец находит в серии своих бросков последовательную пару «Орёл — Решка». Это броски 4 (порядковый номер 2) и 6 (порядковый номер 3). Он сообщает Злому Духу порядковый номер броска 2.
2. Второй мудрец, услышав сообщение первого мудреца, проверяет результат из своей серии бросков под порядковым номером 2. Это бросок 3. Его результат — решка. Значит, чтобы результаты совпали, второй мудрец должен сообщить номер броска из серии первого мудреца с результатом — решка. По паттерну он точно знает, что это результат с порядковым номером 3. Этот номер второй мудрец и сообщает Злому Духу.

Таких паттернов можно придумать сколько угодно. Если заранее договориться о нужной последовательности результатов бросков, то шанс остаться в живых у мудрецов будет равняться 100%.

Вариант 2. Мудрецы не слышат друг друга (классический вариант)

Теперь мы подобрались к тому решению, которое ждал от нас автор задачи. Здесь мы уже не можем гарантировать 100% выживаемость мудрецов.

Подходов к решению много. Ходят слухи, что кому-то удалось найти такое решение, которое обеспечивает вероятность спасения более 70%. Если вы знаете, как добиться такого результата, напишите об этом в комментариях!

Вот один из вариантов решения задачи в классическом варианте. Для упрощения рассмотрим только первые 4 броска. У каждого мудреца — по два броска.

Стратегия мудрецов будет направлена на то, чтобы увеличить шансы на совпадение результатов. Для этого нужно продумать алгоритм выбора первого или второго броска для каждого из мудрецов в зависимости от результатов этих бросков.

Рассмотрим такой алгоритм:

1. Если у первого мудреца результат первого броска — решка, то он сообщает Злому Духу номер 1. Иначе — номер 2.
2. Если у второго мудреца в первом броске выпала решка, а во втором — орёл, то он сообщает Злому Духу номер 1. Во всех остальных случаях — номер 2.

Давайте сведём все возможные варианты работы такого алгоритма в таблицу. В столбцах — результаты первого мудреца, в строках — второго. В скобках указан бросок, который называет мудрец по нашему алгоритму.

В ячейках таблицы — сравнение результатов. Если результаты мудрецов совпали, то указан плюс, если не совпали, то минус.

Нам удалось обеспечить очень неплохой результат — 10 успешных исходов из 16. Мудрецы выживут в 62,5% случаев.  Для нашей задачи можно придумать довольно много последовательностей, которые обеспечат такой же или лучший результат. Чем больше бросков мы включим в нашу стратегию, тем с большей вероятностью мудрецам удастся выжить.