Загадка №1 — Про монетку, Алису и Боба
На последней GDG Google конференции для разработчиков я наткнулся на приклеенную к стене загадку. Очень интересную и простую головоломку. Вот её условие:
Алиса и Боб играют в игру, будучи в одной команде.
Правила таковы: игроков разводят в разные комнаты, где каждый бросает монетку и должен угадать, что выпало у партнёра. Подглядеть, подслушать или как-либо обмануть нельзя.
Если кто-то из них угадал (или они оба) — команда выиграла. Если никто не угадал — проиграла.
Предложите Алисе и Бобу стратегию, как выигрывать в 100% случаев.
ВНИМАНИЕ. Ниже будет дан ответ. Желательно, разгадать загадку самостоятельно.
Первым делом, не до конца прочитав условия, я предложил вариант, когда один из игроков угадывая сторону монеты — давал подсказку своему партнёру, оглашая собственную выпавшую сторону монетки. Т.е. если бы у Боба выпал «орёл» — он бы «предположил», что у Алисы выпадет орёл. А Алиса, услышав, версию Боба поняла, что у него выпал именно орёл. Просто, хитро, но не удовлетворяет условиям. Во второй раз перечитав данную загадку, я всё-таки понял, что никаких коммуникаций у них не может быть после того, как они разойдётся по комнатам 🙂
Итак, что мы имеем. Вероятность угадать выпавшую сторону для одного человека — 50% (и есть 50% не угадать). В нашей загадке необходимым условием для выигрыша является то, что хотя бы одному из партнёров необходимо будет угадать орёл выпал или решка. Соответственно, условием для проигрыша является тот факт, что не угадают ОБА. Эта вероятность рассчитывается перемножением 0.5*0.5, т.е. вероятность на проигрыш в случае слепого угадывания равна 25%. В 3\4 случаев (75%) мы будем выигрывать. Но что же делать с оставшимися 25%?
Монетка может выпасть только на аверс или реверс, вероятности с ребром и прочие другие варианты отбрасываем сразу. Т.е. у нас есть некоторая система, которая может находится только в двух состояниях. Это бинарная система, а значит можно построить таблицу истинности. Пусть «орёл» будет нулём (для удобства «о»=0) и «решка» — единицей (1). Таким образом мы может построить таблицу истинности для всех возможных вариантов событий. Таблица с колонками: АВ (Алиса выпало), АП (Алиса предполагает), БВ (Боб выпало), БП (Боб предполагает) и Р (результат):
| № | АВ | АП | БВ | БП | Р |
|---|---|---|---|---|---|
| 01 | 0 | 0 | 0 | 0 | Победа |
| 02 | 0 | 0 | 0 | 1 | Победа |
| 03 | 0 | 0 | 1 | 0 | Победа |
| 04 | 0 | 0 | 1 | 1 | Проигрыш |
| 05 | 0 | 1 | 0 | 0 | Победа |
| 06 | 0 | 1 | 0 | 1 | Проигрыш |
| 07 | 0 | 1 | 1 | 0 | Победа |
| 08 | 0 | 1 | 1 | 1 | Победа |
| 09 | 1 | 0 | 0 | 0 | Победа |
| 10 | 1 | 0 | 0 | 1 | Победа |
| 11 | 1 | 0 | 1 | 0 | Проигрыш |
| 12 | 1 | 0 | 1 | 1 | Победа |
| 13 | 1 | 1 | 0 | 0 | Проигрыш |
| 14 | 1 | 1 | 0 | 1 | Победа |
| 15 | 1 | 1 | 1 | 0 | Победа |
| 16 | 1 | 1 | 1 | 1 | Победа |
Мы ожидаемо получили 4 проигрыша (25%) из всех 16 (100%) возможных вариантов и 12 побед (75%). Теперь сделаем отдельную выборку, т.к. нас интересуют все ситуации с проигрышем:
| № | АВ | АП | БВ | БП | Р |
|---|---|---|---|---|---|
| 04 | 0 | 0 | 1 | 1 | Проигрыш |
| 06 | 0 | 1 | 0 | 1 | Проигрыш |
| 11 | 1 | 0 | 1 | 0 | Проигрыш |
| 13 | 1 | 1 | 0 | 0 | Проигрыш |
Это и есть те 0.5*0.5 процент случаев, когда никто из игроков не угадал. Для того, чтобы наши множества пересеклись, необходимо изменить стратегию на следующую: Алиса должна всегда говорить то, что у неё выпало и тогда во всех случаях, когда её результат и Боба совпадают — она будет выигрывать. А Боб должен всегда называть противоположный своему ответ, тем самым Боб будет выигрывать во всех случаях, когда результат выпадения монет у игроков будет отличаться.
Ответ на загадку следующий: Алиса отвечает ЕЁ МОНЕТА xor 1, а Боб — ЕГО МОНЕТА xor 0.