Две задачи на координацию: монеты и бесконечность

Даниил Фенелонов 12 мая 2026 г. 8 минут чтения

#Теория вероятностей #Собеседования #Задачи #ML

Содержание

Всем привет! 👋 Сегодня разберём две задачи. Первая кажется безнадёжной, но решается в одну строчку. Вторая кажется невозможной, но у неё есть красивейшие решения. Обе про одно и то же: как два человека, которые не могут общаться, могут действовать координированно, если договорились о стратегии заранее. По моему мнению это одни из самых завораживающих и интересных задач.

Задача 1. Две монеты

Двоих поймали и дали каждому по монете (обычная, честная). У них есть 5 минут, чтобы договориться о стратегии. После этого их разводят по разным комнатам, где они не видят и не слышат друг друга. Каждый подбрасывает свою монету. После этого каждый должен угадать, что выпало у другого. Если хотя бы один из них угадал, оба свободны. Если оба ошиблись, оба погибают.

О чём они должны договориться, чтобы выжить в 100% случаев?

Первая реакция

Кажется невозможным. Результат подбрасывания случаен, информации о монете другого нет. Лучшее, на что можно рассчитывать, это 50/50 для каждого, а значит вероятность, что оба ошибутся, равна 25%. Выживание 75%. Неплохо, но не 100%.

Но 100% возможно.

Решение

Они договариваются о следующем:

Первый всегда называет то, что выпало у него самого. Выпал орёл, он говорит: «У второго орёл».

Второй всегда называет противоположное тому, что выпало у него. Выпал орёл, он говорит: «У первого решка».

Проверяем все четыре исхода:

У первого	У второго	Первый говорит	Угадал?	Второй говорит	Угадал?
О	О	О	✅	Р	❌
О	Р	О	❌	O	✅
Р	О	Р	❌	Р	✅
Р	Р	Р	✅	О	❌

В каждой строке ровно один угадывает. Гарантированное выживание.

Почему это работает

Ключевая идея: стратегии комплементарны. Первый покрывает случаи, когда монеты совпали (ОО и РР). Второй покрывает случаи, когда монеты различаются (ОР и РО). Вместе они покрывают всё пространство исходов.

Это очень частый прием, разделение пространства вариантов между двумя игроками так, чтобы суммарно покрыть 100%.

Если оба использовали бы одинаковую стратегию (оба называют своё или оба называют противоположное), они угадывали бы одновременно и ошибались бы одновременно. 75%, не 100%. Асимметрия стратегий, это то, что превращает 75% в 100%.

Задача 2 ⭐. Бесконечная последовательность

Двоих поймали и посадили в разные комнаты. Подбросили честную монету бесконечное количество раз: бросок 1, бросок 2, бросок 3, …

Первому сообщили результаты всех чётных бросков (2, 4, 6, …). Второму сообщили результаты всех нечётных (1, 3, 5, …).

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

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

Почему это сложнее

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

Наивная стратегия «оба называют бросок 1 (или 2)» даёт ровно 50%: монета честная, результаты независимы. Можно ли лучше?

Можно. И существенно.

Решение 1: простая стратегия

Используем только первые два броска каждого игрока.

Первый (знает чётные: бросок 2, бросок 4, …):

Если бросок 2 = О → называет бросок 1
Если бросок 2 = Р → называет бросок 3

Второй (знает нечётные: бросок 1, бросок 3, …):

Если бросок 1 и бросок 3 разные (ОР) → называет бросок 2
Если бросок 1 и бросок 3 одинаковые (ОО, РР, РО) → называет бросок 4

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

Мы можем сами в этом убедиться.

Бросок 1	Бросок 2	Бросок 3	Бросок 4	Первый указал на	Второй указал на	Совпали?
О	О	О	О	бросок 1 (О)	бросок 4 (О)	✅
О	О	О	Р	бросок 1 (О)	бросок 4 (Р)	❌
О	О	Р	О	бросок 1 (О)	бросок 2 (О)	✅
О	О	Р	Р	бросок 1 (О)	бросок 2 (О)	✅
О	Р	О	О	бросок 3 (О)	бросок 4 (О)	✅
О	Р	О	Р	бросок 3 (О)	бросок 4 (Р)	❌
О	Р	Р	О	бросок 3 (Р)	бросок 2 (Р)	✅
О	Р	Р	Р	бросок 3 (Р)	бросок 2 (Р)	✅
Р	О	О	О	бросок 1 (Р)	бросок 2 (О)	❌
Р	О	О	Р	бросок 1 (Р)	бросок 4 (Р)	✅
Р	О	Р	О	бросок 1 (Р)	бросок 2 (О)	❌
Р	О	Р	Р	бросок 1 (Р)	бросок 2 (О)	❌
Р	Р	О	О	бросок 3 (О)	бросок 4 (О)	✅
Р	Р	О	Р	бросок 3 (О)	бросок 4 (Р)	❌
Р	Р	Р	О	бросок 3 (Р)	бросок 2 (Р)	✅
Р	Р	Р	Р	бросок 3 (Р)	бросок 2 (Р)	✅

Если аккуратно посчитать все комбинации (а их 16: четыре броска, каждый О или Р), вероятность совпадения получается 5/8 = 62.5%.

Решение 2: оптимальная стратегия на 2/3

Вот где супер красота.

Стратегия: каждый находит позицию, на которой у него впервые выпал орёл, и называет ту же позицию у другого.

Конкретно:

Первый (знает чётные) смотрит на последовательность бросков 2, 4, 6, 8, … Находит первый орёл. Допустим, это бросок 4. Он называет бросок 3 (нечётный с тем же «порядковым номером» в последовательности, то есть второй нечётный).

Чуть формальнее: первый смотрит на позиции 2, 4, 6, … Если первый орёл на $k$ -й позиции в его последовательности (бросок $2k$ ), он называет бросок $2k - 1$ .

Второй делает то же самое зеркально: смотрит на 1, 3, 5, …, находит первый орёл, и называет соответствующий чётный бросок.

Почему вероятность равна 2/3

Пусть $X$ — позиция первого орла у первого игрока, $Y$ — позиция первого орла у второго. Оба имеют геометрическое распределение.

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

Ключевое наблюдение: если $X = Y$ (оба нашли первый орёл на одной и той же позиции в своих последовательностях), то оба указывают на «парные» броски, и оба эти броска — орлы (потому что каждый указывает на позицию, где у другого тоже первый орёл). Совпадение.

Если $X \neq Y$ , позиции, на которые указали игроки, не связаны с первым орлом друг друга. Результаты на этих позициях — независимые честные монеты. Совпадают с вероятностью 1/2.

Вероятность $P(X = Y)$ считается через сумму ряда:

P(X = Y) = \sum_{k=1}^{\infty} P(X = k) \cdot P(Y = k) = \sum_{k=1}^{\infty} \left(\frac{1}{2^k}\right)^2 = \sum_{k=1}^{\infty} \frac{1}{4^k} = \frac{1/4}{1 - 1/4} = \frac{1}{3}

Когда $X = Y$ , оба указывают на позицию первого орла у другого, значит оба броска — орлы. Гарантированное совпадение. Когда $X \neq Y$ (вероятность 2/3), результаты на указанных позициях — независимые честные монеты, совпадают с вероятностью 1/2. Полная вероятность совпадения:

P(\text{совпадение}) = \frac{1}{3} \cdot 1 + \frac{2}{3} \cdot \frac{1}{2} = \frac{1}{3} + \frac{1}{3} = \frac{2}{3}

Вероятность спасения: 2/3

Почему это красиво

Наивная стратегия даёт 50%. Простая стратегия на первых бросках даёт 62.5%. Оптимальная стратегия с геометрическим распределением даёт 66.7%.

И 2/3 — это доказуемый верхний предел для этой задачи. Лучше невозможно.

Задача выглядит так, будто 50% — это потолок (монеты честные, информации о чужих бросках нет). Но стратегия создаёт корреляцию между выборами игроков через структуру наблюдений. Оба видят разные половины одной последовательности, и это позволяет координироваться без общения.

Что объединяет обе задачи

В обеих задачах интуиция говорит: «Без информации о другом невозможно действовать лучше случайного». И в обеих интуиция ошибается.

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

Поделиться в Telegram