Загадка №1 — Про монетку, Алису и Боба

30 октября, 2017DEV

На последней GDG Google конференции для разработчиков я наткнулся на приклеенную к стене загадку. Очень интересную и простую головоломку. Вот её условие:

Алиса и Боб играют в игру, будучи в одной команде.
Правила таковы: игроков разводят в разные комнаты, где каждый бросает монетку и должен угадать, что выпало у партнёра. Подглядеть, подслушать или как-либо обмануть нельзя.
Если кто-то из них угадал (или они оба) — команда выиграла. Если никто не угадал — проиграла.
Предложите Алисе и Бобу стратегию, как выигрывать в 100% случаев.

ВНИМАНИЕ. Ниже будет дан ответ. Желательно, разгадать загадку самостоятельно.

Первым делом, не до конца прочитав условия, я предложил вариант, когда один из игроков угадывая сторону монеты — давал подсказку своему партнёру, оглашая собственную выпавшую сторону монетки. Т.е. если бы у Боба выпал «орёл» — он бы «предположил», что у Алисы выпадет орёл. А Алиса, услышав, версию Боба поняла, что у него выпал именно орёл. Просто, хитро, но не удовлетворяет условиям. Во второй раз перечитав данную загадку, я всё-таки понял, что никаких коммуникаций у них не может быть после того, как они разойдётся по комнатам 🙂

Итак, что мы имеем. Вероятность угадать выпавшую сторону для одного человека — 50% (и есть 50% не угадать). В нашей загадке необходимым условием для выигрыша является то, что хотя бы одному из партнёров необходимо будет угадать орёл выпал или решка. Соответственно, условием для проигрыша является тот факт, что не угадают ОБА. Эта вероятность рассчитывается перемножением 0.5*0.5, т.е. вероятность на проигрыш в случае слепого угадывания равна 25%. В 3\4 случаев (75%) мы будем выигрывать. Но что же делать с оставшимися 25%?

Монетка может выпасть только на аверс или реверс, вероятности с ребром и прочие другие варианты отбрасываем сразу. Т.е. у нас есть некоторая система, которая может находится только в двух состояниях. Это бинарная система, а значит можно построить таблицу истинности. Пусть «орёл» будет нулём (для удобства «о»=0) и «решка» — единицей (1). Таким образом мы может построить таблицу истинности для всех возможных вариантов событий. Таблица с колонками: АВ (Алиса выпало), АП (Алиса предполагает), БВ (Боб выпало), БП (Боб предполагает) и Р (результат):

АВАПБВБПР
010000Победа
020001Победа
030010Победа
040011Проигрыш
050100Победа
060101Проигрыш
070110Победа
080111Победа
091000Победа
101001Победа
111010Проигрыш
121011Победа
131100Проигрыш
141101Победа
151110Победа
161111Победа

Мы ожидаемо получили 4 проигрыша (25%) из всех 16 (100%) возможных вариантов и 12 побед (75%). Теперь сделаем отдельную выборку, т.к. нас интересуют все ситуации с проигрышем:

АВАПБВБПР
040011Проигрыш
060101Проигрыш
111010Проигрыш
131100Проигрыш

Это и есть те 0.5*0.5 процент случаев, когда никто из игроков не угадал. Для того, чтобы наши множества пересеклись, необходимо изменить стратегию на следующую: Алиса должна всегда говорить то, что у неё выпало и тогда во всех случаях, когда её результат и Боба совпадают — она будет выигрывать. А Боб должен всегда называть противоположный своему ответ, тем самым Боб будет выигрывать во всех случаях, когда результат выпадения монет у игроков будет отличаться.

Ответ на загадку следующий: Алиса отвечает ЕЁ МОНЕТА xor 1, а Боб — ЕГО МОНЕТА xor 0.

Leave a comment

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Prev Post Next Post