Белый дом предложил решить головоломку

Заместитель директора по технологиям администрации Барака Обамы, Эд Фелтен, опубликовал в своем официальном блоге на сайте Белого дома головоломку. Условия задачи следующие:

Два человека, например, Вася и Маша, играют в одной команде. Они могут заранее обсудить стратегию поведения. После этого Вася и Маша расходятся по разным комнатам. Каждый из них подбрасывает монетку и записывает результат — «орел» или «решка». Затем Вася и Маша пытаются угадать, что выпало у партнера. Если хоть кто-нибудь из них угадал, то они выиграли. Если ни Маша не угадала, что выпало у Васи; ни Вася не угадал, что выпало у Маши, то команда проиграла.

Васе и Маше нужно помочь придумать стратегию, чтобы они выигрывали каждый раз.

Эд Фелтен для примера приводит стратегию, которая не работает. Если Вася и Маша договорятся всегда предполагать, что у партнера выпала «решка», то в 25% случаев они будут проигрывать (так как у обоих будет выпадать «орел»).