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

[avva]

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

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

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

Пример:

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

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

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

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

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

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

Comments

[buddha239.livejournal.com]

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

[avva.livejournal.com]

Близко к 60%, но не совсем столько :)

[buddha239.livejournal.com]

(1/4 + 1/16 + 1/64+...)/2 + 1/2 - разве нет?

[avva.livejournal.com]

Если искомая вероятность p, получаем p = 1/4(p + 1/2 + 1/2 + 1). В скобках вероятности успеха в дальнейшем, если в первом бите два игрока имеют соответственно 00, 01, 10, 11.

[buddha239.livejournal.com]

Ой, я не умею геометрические прогрессии суммировать.:) Да, 2/3 получается.