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

[avva]

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

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

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

Пример:

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

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

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

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

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

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

Comments

[vnarod.livejournal.com]

Они называют число один раз или последовательность чисел? Если последовательность, то знают ли они результат после каждого числа?

[sleeping-death.livejournal.com]

лично я не понял два момента.

1. что значит "оба всегда отвечать 1"? ведущий спрашивает число, а они раз за разом оба говорят "1"?

2.Знают ли игроки результат каждого хода? Исходя из текста - вроде знают. Но прямо это не сказано.

[fortunatus.livejournal.com]

Больше 50% можно получить, только если игрокам говорят, какие цифры были названы на предыдущем ходу.

Тогда самая простая стратегия:

На 1 ходу оба называют номер первого нуля в своей последовательности. Выигрывают с вероятностью 50%.

На 2 ходу А называет номер первого нуля в послед-сти В (который узнал после предыдущего хода), а В - аналогично. Выигрыш 100%.

На 3 ходу А и В называет номера вторых нулей у себя (опять 50%), на 4 - номера вторых нулей у соседа (100%), и т. д.

Общая вероятность выигрыша стремится к 75%.

[fortunatus.livejournal.com]

Более эффективная стратегия:

А берёт первые N бит своей послед-сти, переводит в десятичную систему и называет. То же делает В. На этом ходу вероятность совпадения 50%, но теперь у них есть полная информация обо всех первых N бросках друг друга. Следующие N ходов они получают 100% выигрыша, итого общая вероятность за 1+N ходов равна (N+0,5)/(N+1), и при стремлении N к бесконечности стремится к единице.

Таким образом, верхнего предела нет.

[raindog-2.livejournal.com]

Мой лучший алгоритм дает 0.6999816, но его точно можно улучшить. Выглядит, что предел - это 0.7, но почему - пока непонятно :)

[jmyshanya.livejournal.com]

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

[mudasobwa.livejournal.com]

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

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

[jmyshanya.livejournal.com]

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

а что является критерием выигрыша? судя по этой фразе - набрать хотя бы одно очко...

[livelight]

Очко начисляется за раунд. Каждый раунд включает бесконечную последовательность бросков (даже две). Раундов бесконечное количество.

[fortunatus.livejournal.com]

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

[(Anonymous)]

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

[vika-1-2.livejournal.com]

Они могут, выиграв на втором ходу, дальше бесконечно повторять этот ход просто.

[(Anonymous)]

Ну вот самое тупое: одинаковая стратегия, смотрим только на первые два бита, если они 01, то говорим 2, иначе 1. Выигрываем при: 01/01, 01/(00|10) и наоборот, 00/00, (10|11)/(10|11), т.е. в 1 + 2*2 + 1 + 2*2 = 10 случаях из 16.

[(Anonymous)]

Непонятно условие всё-таки. Играют они один раз или много? Если много, то строится ли вся бесконечная последовательность заново для каждого из игроков? Если не строится заново, то что им мешает называть одну и ту же однажды найденную выигрышную комбинацию. Известен ли им результат предыдущего раунда? Или попытка всего одна и надо с единственной попытки, не имея никакой информации о последовательности партнёра, и не зная заранее числа, которое он назвал, получить >50%?

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

[mikhaelo.livejournal.com]

Надо разъяснить в условии задачи, каждый следующий ход делается после того как известен результат предыдущего или все ходы делаются вслепую? Это в корне меняет подход.

[(Anonymous)]

Ах что это я, самое тупое - это называть позицию первого ноля, тогда вероятность совпадения названных чисел p = 1/4 + 1/16 + ... = 1/3, а вероятность победы p + (1-p)/2 = 2/3(ибо если назвали разные числа, то 50%).

[livelight]

Предыдущая предложенная стратегия почти совпадала со стратегией "называть позицию первой единицы" :)

[vika-1-2.livejournal.com]

Да, так и есть. Но почему это работает?

[mirdin.livejournal.com]

А они знают какое число называл другой игрок в предыдущую попытку?

[dead-knight.livejournal.com]

Я так понимаю, последовательность уже есть?

Тогда договариваемся называть только позиции 0/решек до тех пор, пока у обоих игроков они есть. Если у одного игрока 0/решки закончились, то он называет позицию с 1/орлом. С этого момента называем позиции только единиц.

И да, прекращаем играть на 2-м несовпадении, значит у одного остались только 1/орлы, а у второго 0/решки.

[buddha239.livejournal.com]

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

[vitaliborovikov.livejournal.com]

Если в последовательности появление 0 или 1 равновероятно, то безразлично какой элемент будет выбран. Вероятность появления 1 всегда будет 0,5. В таком случае вероятность совпадения двух любых элементов последовательности равна 0,5. Или я не понял условия задачи?

[asiafilm-tv.livejournal.com]

Сразу пришло в голову, что надо называть позицию первой единицы в своей последовательности (ну, или нуля - неважно, главное договориться об одном и том же). Поскольку бросков бесконечное количество, то единица или ноль там обязательно будут. Но не понял почему это должно работать. Написал программку для проверки - да, действительно, если они называют всегда одно и то же число (ну, или случайное) - то вероятность выигрыша 1/2. Если позицию первой единицы - то 2/3.

Уже в комментариях нашел объяснение почему :)

Интересно, можно ли больше.

[asiafilm-tv.livejournal.com]

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

[dead-knight.livejournal.com]

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