Бесконечная последовательность бросков

Добрый день!

В прошлый раз мы рассмотрели, как можно начать перебор в простой задачке. Смысл здесь в следующем: раз к нам быстро не пришла светлая мысль, то давайте поможем ей — рассмотрим несколько возможностей. Нередко это приводит к тому, что мы начинаем «чувствовать» задачку, а от этого уже и до решения рукой подать.

Следующая задачка о бесконечных последовательностях чем-то похожа на эту про один бросок, поэтому есть смысл повторить этот же подход. Каждый из наших математиков применяет функцию, которая принимает бесконечную последовательность бит, а отдаёт натуральное число — индекс в последовательности другого математика. Математикам надо выбрать такие функции, чтобы как можно чаще выигрывать. А наша задача — перебрать хоть какие-то возможные функции, чтобы лучше понять условие задачи.

Разных таких функций может быть очень много, поэтому давайте временно упростим игру — пусть наши математики смотрят только на результат первого броска, а всю остальную последовательность игнорируют. Соответственно, имея на входе только один бит (будем обозначать буквами O и R от слов obverse и reverse), он будет называть число, задаваемое одним битом (мы считаем, что последовательность начинается с 1, поэтому на выходе у функций математиков будет 1 или 2).

Пусть, например, первый математик, увидев результат первого броска «O», всегда называет индекс 1, а увидев «R» — отвечает 2. А второй математик пусть действует наоборот. Ниже приведены две таблицы для всех возможных 16 входных состояний, названные индексы обоих математиков (выделено жирным), а также результаты броска другого математика по названному индексу.



А в нижней таблице приводятся результаты сравнения этих бросков по названным индексам. Как видите, вероятность победы при таких функциях получилась меньше 50% (6/16=37.5%). Уже в этот момент нам должно стать странно, ведь совсем недавно было совершенно очевидно, что при любых договорённостях математики выигрывают с вероятностью 50% (мол, они ничего не знают про последовательности друг друга, поэтому могут называть любые индексы — как раз будут случайно совпадать в половине случаев). А тут вдруг они небольшим усилием смогли выигрывать реже, чем при назывании случайных индексов. Как так?

Полагаю, сейчас стало понятнее, как здесь имеет смысл вести перебор. Если рассматривать больше, чем один первый бросок, то можно добиться более заметных результатов. Скорее всего, такой перебор в Excel вести будет неудобно, но почти любой другой язык программирования сгодится. Пожалуйста, делитесь своими результатами перебора и программами для их получения в комментариях. С какой максимальной вероятностью математики могут побеждать?

Если вы хотите ещё почитать о том, как считать вероятности, то предлагаю вспомнить разбор другой задачки о бросках монетки (вопрос был в том, проще выиграть три раза из четырёх или пять раз из восьми). Там мы сперва перебирали на Javascript, а потом аккуратно всё проверили. Самое ценное в той заметке в комментариях, как обычно.

Хорошего дня!