Загадка 1. Нам дана неправильная монетка, при бросании которой орел выпадает с вероятностью p. При помощи этой монетки нужно «построить» механизм моделирования честной монетки.

Решение. Нужное нам решение — это так называемый фокус фон Неймана: бросаем монетку дважды, интерпретируя ОР как орла, а РО как решку. (Если выпадут ОО или РР, пробуем еще раз.) Теперь «орел» и «решка» равновероятны, поскольку в любом заданном испытании то и другое возникает с вероятностью p (1 — p). Следовательно, такая модель монетки работает честно (при условии, что выпадает ОР или РО).

Загадка 2.n человек сидят по кругу. У каждого из них на голове либо красная, либо синяя шляпа, полученные случайно, равномерно и независимо. Каждый может видеть шляпы всех остальных, но не свою собственную. Основываясь только на том, что видит, каждый высказывает свое мнение: является число красных шляп нечетным или нет. Существует ли схема, при которой результат голосования будет верным с вероятностью, большей 1/2?

Решение. Каждый человек определяется с голосованием так: если число видимых ему синих шляп больше, чем число видимых красных шляп, он голосует в соответствии с четностью числа видимых красных шляп. В противном случае — голосует наоборот. Если число красных шляп отличается от числа синих на две или больше, то эта схема срабатывает точно. Если нет, схема может и не сработать. Однако вероятность того, что число красных шляп отличается от числа синих меньше чем на 2, невелика — O (1/√N).