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

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

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

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

Пример:

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

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

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

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

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

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

иногда мертвая птичка это всего лишь мертвая птичка

Жан-Батист Грёз был французский художник 18 века. В 1760-е он прославился сентиментальными портретами девушек, матерей и отцов семейств в бытовых ситуациях, и некоторое время был самым почитаемым творцом среди парижского бомонда. После революции о нем забыли и он умер в нищете.

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



Об этой картине, "Девочка оплакивает мертвую птичку", писали очень много восторженных слов, но никто, наверное, не превзошел Дени Дидро (того самого, основателя Энциклопедии). Его объяснение происходящего на этой картине (из сборника "Салон 1765 года") хочется процитировать целиком. Это тот случай, когда читаешь, и думаешь, что уже невозможно дальше пойти, но ему опять удается.

За 150 лет до Фрейда хочется сказать, что иногда мертвая птичка это всего лишь мертвая птичка.

"Девушка, оплакивающая мертвую птичку. Какую прелестную элегию, дивную идиллическую поэму создал бы на этот сюжет Гесснер! Полотно Грёза — словно иллюстрация к отрывку из какого-то его стихотворения. Эта картина поистине одна из приятнейших и, бесспорно, самая интересная во всем Салоне. Девушка изображена на ней лицом к зрителю, голова ее опирается на левую руку, а перед ней на решетке клетки лежит птичка с поникшей головкой, распластанными крыльями и беспомощно вздернутыми лапками. Вглядитесь, как естественна поза девушки, как прелестна ее головка и изысканна прическа, как выразительно ее лицо! Она и впрямь глубоко страдает и вся проникнута своим горем. А как написана клетка, где успокоилась птичка, как изящно обвивает ее гирлянда зелени! А рука девушки, ну что за рука! Только посмотрите на эти словно живые пальцы и эти ямочки, на то, как чуть порозовели пальцы там, где на них опирается голова! Как все это очаровательно, и не склоняйся мы перед горем страдалицы, нам так и хотелось бы поцеловать ее руку. В этой девушке все очаровывает, даже самый ее наряд. Как воздушен и легок ее шарф, как он славно наброшен! Увидев эту картину впервые, так и хочется воскликнуть: «Прелестно!» — а возвратившись к ней, вновь и вновь повторять это. Вот уж и ловишь себя на том, что начинаешь заговаривать с малюткой и утешать ее.

Мне самому, помнится, не раз случалось говорить ей: — Милое дитя, как глубока и безутешна ваша скорбь! Что скрывает ваша грусть и задумчивость? Как, и все это из-за птички? Ведь вот вы не плачете, вы погружены в горестные думы. Смелее, малютка, откройте мне свое сердце, скажите по правде: разве лишь смерть этой птички так глубоко отрешила вас от всего вокруг? Но вы потупили взор и ничего не отвечаете... слезы вот-вот потекут из ваших глаз. Я не довожусь вам отцом, я ни нескромен, ни строг, но дайте же мне сказать, как было дело. Ваш поклонник любил и уверял вас в своей любви, он так страдал, и как же было перенести муки того, кого любишь? Но дайте продолжить, не протягивайте ручку к моим губам! В то утро вашей матери не было дома; он пришел и застал вас одну. Как он был пылок, красив, как прелестен и нежен! Сколько любви горело в его глазах, сколько подлинной страсти сквозило в его речах! Он был у ваших ног — как же иначе? — и говорил слова, идущие прямо в душу. Он держал вашу руку, и временами вы ощущали на ней жар его слез. Ваша мать все не возвращалась и не возвращалась, в чем же вы здесь виноваты? Вот вы уже и плачете, а ведь я не для того говорю все это. Да и что толку в слезах? Он дал вам слово и уж ни в чем от него не отступится. Случись человеку счастье повстречать подобное вам дитя, приникнуть к нему, полюбить... Поверьте, это навеки.

— А моя птичка? — Ну-ну, улыбнитесь! Ах, друг мой, как жаль, что не довелось вам увидеть, как прелестны были ее улыбка и слезы! Но я продолжаю: — Что там ваша птичка? Разве помнят о ней, когда человек забывает о самом себе? Ваша мать вот-вот должна была воротиться, ваш любимый ушел. Как же он был окрылен и доволен! Каких усилий стоило ему покинуть свою милую! Да не глядите вы так на меня — я все это знаю! Сколько раз он вставал и снова садился, сколько раз вновь и вновь твердил слова прощания и все не мог покинуть вас, сколько раз уходил и опять возвращался! Я вижу, как он теперь беседует со своим отцом, столь оживленно и весело, что трудно не заразиться этим весельем.

— ...А моя мать? — Ну что ж, она возвратилась, стоило ему только уйти, и застала вас погруженной в себя, такой, как вы были только что. Она что-то говорила вам, но вы словно не слышали, просила о чем-то, но вы делали совсем другое. Иногда слезинки дрожали у вас на ресницах, и вам приходилось то и дело отворачиваться, чтобы украдкой смахнуть их. Все это в конце концов вывело из себя вашу матушку, и она принялась вас отчитывать — вот и представился случай вволю поплакать и облегчить ваше сердце. Мне продолжать? Боюсь, как бы это не заставило вас страдать сызнова, но уж если вы сами желаете — что ж! Ваша мать огорчилась, увидев вас всю в слезах, и подошла, чтобы утешить свое дитя. Она взяла ваши руки в свои, прикоснулась губами ко лбу и щекам, но вы только пуще расплакались. Вы наклонили головку, личико ваше слегка порозовело — вот-вот, совсем как сейчас. Вы прильнули к ее груди. Сколько ласки было в материнских словах, и как вновь и вновь страдали вы от этого! что вам было в ту минуту до бедной птички, которая тщетно махала крылышками, звала вас, словно желая дать знак и горько сожалея о вашей забывчивости! Вся в своих мыслях, вы не слышали и не замечали ее. Вы не сменили ей воду и не подсыпали зернышек — и вот этим утром ее не стало. Вы все не опускаете глаз? Что ж я могу еще добавить? Ах, ну конечно, это он сам подарил вам птичку, но не печальтесь, он найдет другую, еще прелестней. И это еще не все? Вы устремляете на меня свой взор, полный грусти, и словно вопрошаете... Мне не под силу догадаться. Вдруг смерть этой птички таит в себе еще что-то? Что же мне делать и как о том дознаться? Быть может, он был неверен? Да нет, это сущее наваждение, такого быть не может! Но, друг мой, уж не смеетесь ли вы, представляя себе почтенного господина, которому пришла охота утешать написанную на холсте девушку, потерявшую птичку или еще что-нибудь? Но, признайтесь, ведь она и вправду прекрасна и достойна любопытства! Я не любитель доставлять страдание, но был бы не прочь стать причиной ее горя.

Замысел этого маленького полотна так тонок, что далеко не всем удалось в него проникнуть. Многие полагали, что юное создание оплакивает лишь своего чижика."