?

Log in

No account? Create an account
задачка: угадывание битов - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка: угадывание битов [дек. 29, 2017|08:39 am]
Anatoly Vorobey
[Tags|, ]

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

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

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

Пример:

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

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

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

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

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

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

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: vnarod
2017-12-29 06:50 am
Они называют число один раз или последовательность чисел? Если последовательность, то знают ли они результат после каждого числа?
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 10:55 am
Один раз. Я изменил условие, чтобы прояснить это.
(Ответить) (Parent) (Thread)
[User Picture]From: sleeping_death
2017-12-29 06:52 am
лично я не понял два момента.

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

2.Знают ли игроки результат каждого хода? Исходя из текста - вроде знают. Но прямо это не сказано.
(Ответить) (Thread)
[User Picture]From: jmyshanya
2017-12-29 07:25 am

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

(Ответить) (Parent) (Thread)
[User Picture]From: fortunatus
2017-12-29 07:05 am
Больше 50% можно получить, только если игрокам говорят, какие цифры были названы на предыдущем ходу.

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

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

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

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

Общая вероятность выигрыша стремится к 75%.
(Ответить) (Thread)
[User Picture]From: vika_1_2
2017-12-29 08:17 am
Они могут, выиграв на втором ходу, дальше бесконечно повторять этот ход просто.
(Ответить) (Parent) (Thread)
[User Picture]From: fortunatus
2017-12-29 07:14 am
Более эффективная стратегия:

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

Таким образом, верхнего предела нет.
(Ответить) (Thread)
[User Picture]From: mudasobwa
2017-12-29 07:30 am
Никаким образом не оговорено, что они не могут повторяться (более того, фраза «они договорятся оба всегда отвечать „1“» неявно намекает на то, что такого ограничения нет).

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

(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: raindog_2
2017-12-29 07:19 am
Мой лучший алгоритм дает 0.6999816, но его точно можно улучшить. Выглядит, что предел - это 0.7, но почему - пока непонятно :)


Edited at 2017-12-29 07:21 (UTC)
(Ответить) (Thread)
[User Picture]From: con_vertor
2017-12-29 09:56 am
какой алгоритм?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: jmyshanya
2017-12-29 07:41 am

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


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

(Ответить) (Thread)
[User Picture]From: livelight
2017-12-29 07:53 am
Очко начисляется за раунд. Каждый раунд включает бесконечную последовательность бросков (даже две). Раундов бесконечное количество.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2017-12-29 08:31 am
Ну вот самое тупое: одинаковая стратегия, смотрим только на первые два бита, если они 01, то говорим 2, иначе 1. Выигрываем при: 01/01, 01/(00|10) и наоборот, 00/00, (10|11)/(10|11), т.е. в 1 + 2*2 + 1 + 2*2 = 10 случаях из 16.
(Ответить) (Thread)
From: (Anonymous)
2017-12-29 09:05 am
Ах что это я, самое тупое - это называть позицию первого ноля, тогда вероятность совпадения названных чисел p = 1/4 + 1/16 + ... = 1/3, а вероятность победы p + (1-p)/2 = 2/3(ибо если назвали разные числа, то 50%).
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2017-12-29 09:01 am
Непонятно условие всё-таки. Играют они один раз или много? Если много, то строится ли вся бесконечная последовательность заново для каждого из игроков? Если не строится заново, то что им мешает называть одну и ту же однажды найденную выигрышную комбинацию. Известен ли им результат предыдущего раунда? Или попытка всего одна и надо с единственной попытки, не имея никакой информации о последовательности партнёра, и не зная заранее числа, которое он назвал, получить >50%?

Задача становится более осмысленной, если играют они много раз, последовательность не перестраивается, повторно называть одни и те же числа запрещено. Для других случаях не понимаю даже, как к этой задаче подступиться.
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 10:57 am
Неважно, сколько раз играют - "вероятность победы" строится из предположения, что много раз. В каждой игре обе последовательности строятся заново и выбирается только одно число. Отдельные игры друг с другом никак не связаны и стратегия должна учитывать только последовательность, которую видит данный игрок (и то, о чем он договорился заранее с партнером).

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

Именно так.
(Ответить) (Parent) (Thread)
From: mikhaelo
2017-12-29 09:01 am
Надо разъяснить в условии задачи, каждый следующий ход делается после того как известен результат предыдущего или все ходы делаются вслепую? Это в корне меняет подход.
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 10:58 am
Попытался разъяснить. В игре есть только один "ход". Следующий розыгрыш игры будет с другими последовательностями и никак не связан с предыдущим.
(Ответить) (Parent) (Thread)
[User Picture]From: mirdin
2017-12-29 09:37 am
А они знают какое число называл другой игрок в предыдущую попытку?
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 10:59 am
Нет. Все, что они знают - это свою последовательность, и то, о чем они заранее договорились с партнером.
(Ответить) (Parent) (Thread)
[User Picture]From: dead_knight
2017-12-29 09:41 am
Я так понимаю, последовательность уже есть?

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

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


Edited at 2017-12-29 09:46 (UTC)
(Ответить) (Thread)
[User Picture]From: asiafilm_tv
2017-12-29 10:31 am
В бесконечной последовательности решки закончиться не могут.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: buddha239
2017-12-29 09:42 am
Вроде, если каждый называет наименьший из номеров, под которым встретится орел, то 60% (так как если эти числа совпали, то они выиграли, а если нет, то есть два варианта:) равновероятных).
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 10:59 am
Близко к 60%, но не совсем столько :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vitaliborovikov
2017-12-29 10:14 am
Если в последовательности появление 0 или 1 равновероятно, то безразлично какой элемент будет выбран. Вероятность появления 1 всегда будет 0,5. В таком случае вероятность совпадения двух любых элементов последовательности равна 0,5. Или я не понял условия задачи?
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 11:00 am
Возможно, не поняли. Вероятность совпадения двух случайно выбранных элементов последовательностей действительно 0.5, но они выбираются не случайно (пусть и с ограниченной информацией, и "перекрестно" относительно информации друг друга). Можно добиться больше, чем 0.5.
(Ответить) (Parent) (Thread)
[User Picture]From: asiafilm_tv
2017-12-29 10:26 am
Сразу пришло в голову, что надо называть позицию первой единицы в своей последовательности (ну, или нуля - неважно, главное договориться об одном и том же). Поскольку бросков бесконечное количество, то единица или ноль там обязательно будут. Но не понял почему это должно работать. Написал программку для проверки - да, действительно, если они называют всегда одно и то же число (ну, или случайное) - то вероятность выигрыша 1/2. Если позицию первой единицы - то 2/3.

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

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

Edited at 2017-12-29 10:27 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2017-12-29 11:01 am
Любопытно, что 2/3 выглядит очень естественным кандидатом на лучшее возможное решение, но тем не менее это не так. Можно больше.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: shtyrlez
2017-12-29 12:52 pm
Ищем в своей последовательности максимально длинную подпоследовательность единиц и называем индекс последней из них. У второго на этом месте с большей вероятностью будет 0.
(Ответить) (Thread)
From: (Anonymous)
2017-12-29 02:39 pm
Ка в бесконечной последовательности найти максимально длинную подпоследовательность единиц? :)
(Ответить) (Parent) (Thread) (Развернуть)
Страница 1 из 2
<<[1] [2] >>