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

[avva]

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

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

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

Пример:

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

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

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

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

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

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

Comments

[vnarod.livejournal.com]

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

[avva.livejournal.com]

Один раз. Я изменил условие, чтобы прояснить это.

[sleeping-death.livejournal.com]

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

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

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

[jmyshanya.livejournal.com]

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

[(Anonymous)]

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

[fortunatus.livejournal.com]

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

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

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

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

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

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

[vika-1-2.livejournal.com]

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

[fortunatus.livejournal.com]

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

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

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

[mudasobwa.livejournal.com]

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

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

[raindog-2.livejournal.com]

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

[jmyshanya.livejournal.com]

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

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

[livelight]

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

[(Anonymous)]

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

[(Anonymous)]

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

[(Anonymous)]

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

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

[avva.livejournal.com]

Неважно, сколько раз играют - "вероятность победы" строится из предположения, что много раз. В каждой игре обе последовательности строятся заново и выбирается только одно число. Отдельные игры друг с другом никак не связаны и стратегия должна учитывать только последовательность, которую видит данный игрок (и то, о чем он договорился заранее с партнером).

>Или попытка всего одна и надо с единственной попытки, не имея никакой информации о последовательности партнёра, и не зная заранее числа, которое он назвал, получить >50%?

Именно так.

[mikhaelo.livejournal.com]

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

[avva.livejournal.com]

Попытался разъяснить. В игре есть только один "ход". Следующий розыгрыш игры будет с другими последовательностями и никак не связан с предыдущим.

[mirdin.livejournal.com]

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

[avva.livejournal.com]

Нет. Все, что они знают - это свою последовательность, и то, о чем они заранее договорились с партнером.

[dead-knight.livejournal.com]

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

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

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

[asiafilm-tv.livejournal.com]

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

[buddha239.livejournal.com]

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

[avva.livejournal.com]

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

[vitaliborovikov.livejournal.com]

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

[avva.livejournal.com]

Возможно, не поняли. Вероятность совпадения двух случайно выбранных элементов последовательностей действительно 0.5, но они выбираются не случайно (пусть и с ограниченной информацией, и "перекрестно" относительно информации друг друга). Можно добиться больше, чем 0.5.

[asiafilm-tv.livejournal.com]

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

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

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

[avva.livejournal.com]

Любопытно, что 2/3 выглядит очень естественным кандидатом на лучшее возможное решение, но тем не менее это не так. Можно больше.

[shtyrlez.livejournal.com]

Ищем в своей последовательности максимально длинную подпоследовательность единиц и называем индекс последней из них. У второго на этом месте с большей вероятностью будет 0.

[(Anonymous)]

Ка в бесконечной последовательности найти максимально длинную подпоследовательность единиц? :)

[(Anonymous)]

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

[utnapishti.livejournal.com]

Я тоже несколько минут "чувствовал себя глуповато", пока не прочитал внимательно условие. Каждый из них "пытается угадать" не свою последовательность, а последовательность партнёра.

[(Anonymous)]

Не поделитесь ли, в каком именно сообществе засветилась эта задачка? Что-то не нахожу ничего.

[avva.livejournal.com]

https://www.facebook.com/groups/mathpuz

[akimka.livejournal.com]

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

[random-2005.livejournal.com]

Игрок А переводит первые К цифр своего числа в десятичный код и называет его. Так игрок В узнает первые К цифр в числе А. Если в числе В на названном А месте стоит 1, то В должен среди первых известных ему К цифр числа А найти 1 и назвать его номер. Так они оба назовут номер единицы друг друга и выиграют. Аналогично если А попал на ноль у В. Стратегия не сработает только если В не сможет найти 1 среди первых К цифр числа А. Вероятность этого равна 1/2 в степени К. Быстро стремится к нулю.

[(Anonymous)]

В должен назвать свое число не зная, какое число назвал А.

[nick otritsalov (from livejournal.com)]

Александр обязывает Бориса переводить первые три бита в десятичное и называть его.
Во время новой игры Александр исходя из сетки всех возможных вариантов первых трёх битов Бориса и своей последовательности - выбирает наиболее выгодное для общей победы число от 1 до 3.
Точно не считал, но не менее 71% побед вроде как получается

[(Anonymous)]

Во время новой игры и биты новые.

[vasily-bulatov.livejournal.com]

Автор поста похоже путает условия игры или же очень невнятно их объясняет. Вероятно игра которая имеется ввиду описана здесь (по-русски):

https://ru.wikipedia.org/wiki/Игра_Пенни

Однако более ясно и подробно написано по-английски

https://en.wikipedia.org/wiki/Penney's_game

[(Anonymous)]

Нет, это совсем другая игра.

Беспроигрышный вариант

[ilyabirman.livejournal.com]

Не понимаю, что я упускаю, но кажется, я вижу решение, обеспечивающее 100% выигрыш.

А первым называет позицию p, начиная с которой у него самого идёт последовательность из орла и решки. Например, если у А расклад такой:
ООРОРРРОРОРОРОРООООРООРОРО
то А называет p=2, так как с этой позиции есть последовательность ОР.

Пусть, тем временем, у Б расклад такой:
РРОРРРОРРОРООРОРРРООРОРРРРР
Тогда на позиции 2 у него, как видим, решка. Значит игрок А в последовательности игрока Б попал в «решку», и Б теперь должен тоже попасть в решку в последовательности А. Он просто говорит «3», ведь по договорённости А назвал ему позицию, за которой следует решка. Обе игрока «попали в решку друг другу». Победа.

Окей, пусть у Б расклад другой:
ОООООООРРРРРРРОРОРОРООООО
Тогда на позиции 2 у него, как видим, орёл. Значит игрок А в последовательности игрока Б попал в «орла», и Б теперь должен тоже попасть в орла в последовательности А. Он просто говорит «2», ведь по договорённости А назвал ему позицию, на которой у него орёл. Обе игрока «попали в орла друг другу». Победа.

Что я неправильно понял?

(А ещё: давай как-нибудь кофе попьём в Тель-Авиве?)

Re: Беспроигрышный вариант

[ilyabirman.livejournal.com]

А, перечитал и увидел «Эти числа они называют независимо друг от друга». Вопрос снимается, думаю дальше.

(Но вопрос в скобках не снимается)