B4 Шляпы и стратегии с информацией

Идея метода: задачи «в шляпах» — это задачи о группе игроков, каждый из которых видит часть информации (например, цвет шляп на других, но не на себе), и все вместе должны реализовать некоторую коллективную стратегию (угадать свой цвет, передать сообщение, выиграть). Метод состоит в том, чтобы найти способ кодирования общей информации через распределённые наблюдения.

Почему это сложный и важный тип? Потому что здесь нет «передачи информации» между игроками в момент игры — стратегия согласовывается заранее. Задача — использовать структуру видимой информации для «синхронизации» действий.

Интуиция: представь, что команда договорилась перед игрой о коде. Во время игры каждый видит других и, зная код, «вычисляет», что надо сделать. Стратегия — это и есть «код».

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

• Стратегия на основе чётности (XOR): $n$ игроков, каждый видит шляпы остальных. Стратегия: $i$-й игрок объявляет цвет, при котором общий XOR (или сумма по модулю 2) всех шляп равен $i \mod n$. При этом ровно один игрок угадает правильно. Условие:$* 2$ цвета шляп. Когда использовать:* максимизировать число угадавших среди $n$ игроков.
• Обобщение на $k$ цветов: для $k$ цветов используется сумма по модулю $k$. Один из $n$ игроков (выбранный стратегией) угадает правильно. Условие: $k$ цветов, $n$ игроков.
• Нижняя граница: в задаче «угадать хотя бы 1 из $n$» при $2$ цветах оптимальная стратегия гарантирует ровно 1 угадывание, и лучшего результата достичь невозможно без дополнительных условий. Когда использовать: для оценки снизу.
• Стратегия «один жертвует»: один игрок делает вывод о своём цвете, чтобы передать информацию остальным. Например: если сумма видимых шляп чётная, объяви «красный»; если нечётная — «синий». Это сообщает остальным чётность суммы всех шляп. Когда использовать: задача «все угадывают правильно» при наличии одной допустимой ошибки.

• Договориться о базовой переменной: общая сумма (или XOR) всех значений по модулю $k$ — это инвариант, который каждый игрок может «вычислить» по-своему.
• Выделить «жертву»: один игрок угадывает так, чтобы его ответ кодировал нужную информацию для остальных.
• Рассмотреть простейший случай $n=2$: как два игрока могут гарантировать хотя бы одну правильную угадку?
• Разбить игроков на «группы» по роли: один кодирует, остальные декодируют.
• Моделировать стратегию на примере: проверь, что стратегия работает при любом распределении шляп.
• Доказать оптимальность: показать, что без этой стратегии нельзя сделать лучше (теоретико-информационный аргумент).

Поверхностные признаки (что буквально написано):
- «Каждый видит шляпы всех остальных, но не свою».
- «Игроки договариваются о стратегии заранее, но во время игры не могут общаться».
- «Докажите, что команда может гарантировать ... правильных угадок».

Структурные признаки (форма выражения, объекты):
- Небольшая группа игроков (2–10), каждый обладает неполной информацией.
- Информация распределена между игроками несимметрично или симметрично.
- Задача требует совместного действия без коммуникации в реальном времени.

Цель задачи (что от тебя хотят):
- Описать стратегию, гарантирующую заданный результат (не менее $k$ правильных угадок).
- Доказать, что определённый результат недостижим.
- Найти оптимальную стратегию и её гарантированный результат.

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

Источник: тренировочная (классическая задача на шляпы, ВсОШ заключ., Турнир городов).

Как думать (рассуждение ученика$):
1. $Что я вижу? Два игрока, два цвета, нужно хотя бы одно правильное угадывание.$2. *$Наивная стратегия: оба угадывают наугад → вероятность выигрыша $3/4$. Но нужна гарантия (то есть $100\%$)!$3. *$Идея: один называет то, что видит (копирует цвет партнёра), другой — противоположное. Тогда ровно один из них совпадёт с реальностью в любом случае.$4. *$Проверка:* если шляпы КК — первый видит К, называет К (правильно!), второй видит К, называет С (неправильно). Хотя бы один угадал ✓. Аналогично для КС, СК, СС.

Решение:
Стратегия: игрок 1 называет тот цвет, который видит у партнёра; игрок 2 называет цвет, противоположный тому, что видит у партнёра.

Уточнение стратегии: игрок 1 называет цвет партнёра; игрок 2 называет противоположный цвет партнёра.
- КК: игрок 1 → К (✓), игрок 2 → С (✗). Победа.
- КС: игрок 1 → С (✗), игрок 2 → К (✓). Победа.
- СК: игрок 1 → К (✓), игрок 2 → С (✗). Победа.
- СС: игрок 1 → С (✗), игрок 2 → К (✓). Победа.

Ответ: стратегия гарантирует победу во всех $4$ случаях.

Что в этой задаче было главным: «несогласие» между игроками — один копирует, другой отрицает — гарантирует, что они всегда «покрывают» любую комбинацию.

Задача 2. Три игрока, шляпы двух цветов. Каждый видит шляпы двух других. Одновременно каждый может назвать цвет или «пас». Команда выигрывает, если хотя бы один не спасовал и угадал правильно, и никто не ошибся. Найдите стратегию, выигрывающую в $\frac{3}{4}$ случаев.

Источник: классическая задача Паппу–Раддлинга (встречается на Турнире городов, ВсОШ заключ.).

Как думать (рассуждение ученика$):
1. $Что я вижу?* Три игрока, пас разрешён, нужно гарантировать угадывание в $3/4$ случаев.$2. *$Идея: каждый угадывает только если видит у обоих партнёров одинаковые шляпы, и называет противоположный цвет. Если шляпы разные — пасует.$3. *$Проверка:* единственный случай, когда никто не угадывает — все три шляпы разного... нет, при 2 цветах не бывает «все разные» у трёх. Неудача происходит, когда все три одного цвета: тогда каждый видит два одинаковых и называет противоположный (неверно) → проигрыш. Это $2$ из $8$ случаев.

Решение:
Стратегия: если видишь у обоих партнёров одинаковый цвет — называй противоположный; иначе — пас.
- Из 8 равновероятных комбинаций: 2 «все красные» и 2 «все синие» → 2 проигрыша (25%). В оставшихся 6 комбинациях ровно один игрок «видит двух одинаковых» и угадывает правильно → 6 выигрышей (75%).

Ответ: стратегия выигрывает в $6/8 = 3/4$ случаев.

Что в этой задаче было главным: правило «видишь одинаковых — называй противоположное» — это кодирование информации о чётности суммы шляп, переведённое в простое правило для каждого игрока.

• Ошибка: путать гарантированный результат с вероятностным → «В среднем угадают $k$ из $n$» не означает «гарантированно $k$ из $n$». → Как избежать: проверяй стратегию на всех возможных комбинациях шляп, не только на «среднем случае».
• Ошибка: игнорировать запрет на общение во время игры → Стратегия, в которой игроки как-то сигнализируют друг другу в процессе, недопустима. → Как избежать: убедись, что каждый игрок принимает решение только на основе того, что видит, без «подсказок» партнёров.
• Ошибка: не различать «хотя бы один угадал» и «все угадали» → Для «все угадали» нужна другая стратегия (или это невозможно). → Как избежать: внимательно читай условие: «хотя бы один», «ровно один», «все».
• Ошибка: не проверять все $2^n$ комбинаций → Стратегия работает на некоторых, но не на всех. → Как избежать: составь таблицу всех $2^n$ (или $k^n$) комбинаций и проверь каждую.
• Ошибка: считать стратегию «угадывать наугад» оптимальной → Случайная стратегия хуже детерминированной: она не гарантирует ничего. → Как избежать: ищи детерминированную стратегию (согласованную заранее), а не случайную.