задачка: угадывание битов

[avva]

Очень красивая задачка, которая гуляет по тематическим сообществам в последние дни.

Два игрока, А и Б, играют в следующую игру. Они сидят в разных комнатах, и каждый разыгрывает бесконечно длинное число бросков честной монеты, получая таким образом последовательность Орлов и Решек (или 1/0, если вам так удобно), например: ООРОРРОР...

После этого каждый из них смотрит на свою последовательность, думает и называет число, начиная от 1. Эти числа они называют независимо друг от друга. После этого ведущий смотрит, что находится в последовательности Б на порядковом месте, которое назвал А, и что находится у А на месте, которое назвал Б. Если одно и то же, то они выиграли. Если нет, проиграли.

Пример:

А получил ООРОРРОР... и назвал 5.
Б получил РОРОООРР... и назвал 6.

На 5-м месте у Б находится Орел, на 6-м месте у А находится Решка. Они проиграли. Все, игра закончилась, больше они не называют числа.
Следующая игра будет заново разыгрывать две последовательности.

А и Б могут договориться о стратегии своего поведения, до того, как начнут разыгрывать свои броски, естественно. Например, ясно, что если они договорятся в любом случае отвечать "1", независимо от того, что видят в своих бросках, то они выиграют с вероятностью 50%.

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

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

Советую подумать, перед тем, как читать чужие решения - если вы понимаете условие задачи, то скорее всего можете додуматься до какой-то стратегии лучшей, чем 50%, и это приятное достижение.

Comments

[mudasobwa.livejournal.com]

Никаким образом не оговорено, что они не могут повторяться (более того, фраза «они договорятся оба всегда отвечать „1“» неявно намекает на то, что такого ограничения нет).

Поэтому эффективная стратегия при знании результата — повторять совпадение как не особо обученный попугай. Сиречь, результат они, очевидно, не знают. Иначе задачи бы не было.

[fortunatus.livejournal.com]

Не представляю, как можно получить больше 0,5 при незнании результата.