Организуем перебор

Добрый день!

Здорово, что задачку про угадывание чужой монетки вы одолели так быстро. И интересно, что доказательство единственности в вопросе о трёх числах с известной суммой пока так и не появилось.

Но давайте подумаем, а как вообще решать задачи. Методы есть разные: озарение (самый быстрый и эффектный, но как правило требующий серьёзной подготовки), исследование (долго, нудно, но предполагает победу над куда более сложными проблемами). Конечно, это шутка, ведь в серьёзных исследованиях без озарений тоже практически невозможно. Но сегодня я приглашаю подумать про эту задачку о двух математиках с монетками именно в этих терминах.

Итак, каждый из двух математиков подбрасывает монетку, после чего сообщает свою гипотезу о том, что выпало у другого математика. Если хотя бы один из них прав, то они оба победили.

Если вы ещё не дожали эту задачку, то призываю пару минут подумать, прежде чем читать рассуждения ниже.

Переформулировать исходную задачу в следующий вид можно, проводя мысленные эксперименты (т.е. считая вероятности победы при разных нелепых договорённостях между математиками). Это надо, чтобы «пощупать задачку». И вот после этого этапа достаточно легко сформулировать следующее: математик должен применить функцию, которая преобразует один бит в один бит. Т.е., увидев результат своего броска (орёл или решка), он должен дать предположение о броске второго (назвать орла или решку).

Осталось перечислить функции, которые переводят бит в бит:
1) О -> О, Р -> О (т.е. «всегда орёл»);
2) О -> Р, Р -> Р (т.е. «всегда решка»);
3) О -> О, Р -> Р (т.е. «не менять»);
4) О -> Р, Р -> О (т.е. «менять на противоположный»).
(возможно, в комментариях мы обсудим, какие ещё бывают функции, а также, почему мы их сейчас даже не упоминаем)

Соответственно, задача математиков — договориться, кто из них какую функцию применяет. А решающий эту задачку может прямо сейчас перебрать все 4x4=16 вариантов этих договорённостей. Что именно перебирать? Для всех 16 вариантов договорённостей математиков надо перебрать все 4 возможных результата бросков двух монет (ОО, ОР, РО, РР) — так мы узнаем, при каких правилах и сколько раз они выиграли. Например, в прошлой заметке мы показали, как выигрывать в 75% случаев.

Итого, имеем 16х4=64 варианта — не так много. Более того, в процессе перебора должна включиться интуиция, которая быстро его направит к решению. Зачем проделывать этот перебор? Чтобы решить куда более интересную задачку о половине бесконечной последовательности бросков, известной каждому из двух пойманных математиков.

Вы уже начали её исследовать?

Хороших выходных!