История одной задачи с шапками, в которой я решил пойти по максимуму.

Всё началось с классической задачи про гномов и шапки. Я её знал давно, но однажды подумал: а что если вместо обычного решения на модуле 3 впихнуть туда всё, что только можно — теорию конечных полей, топологию, энтропию, Фурье и даже Монте-Карло? Просто чтобы посмотреть, до какого абсурда можно дойти. Получилось… странно. Но интересно.

(Модератору, который в прошлый раз завернул статью с подозрением в написании ИИ — огромный привет, брат! Я всё-таки КФМН, графики не от руки рисовал и расчёты не на бумажке делал — мы не в 19 веке. Всё в Python + matplotlib. Специально убрал научную красоту из статьи((. Не бань второй раз, гномы просят пощады! Или меня ИИ модерировал?😄 )

Пролог: дракон и колонна

Представьте: n гномов стоят в ряд перед пещерой. У каждого шапка — красная, жёлтая или синяя. Последний видит всех впереди, предпоследний — всех кроме последнего, и так далее. Дракон спрашивает последнего: «Какой цвет у тебя?» Угадал — живёшь. Ошибся — обед.

Классика говорит: можно спасти n−1 гнома гарантированно, а последнему дать шанс 1/3. Я же решил: давай сделаем из этого целую научную статью. С тором, гомологиями и всем остальным. Потому что почему бы и нет.

Пространство состояний (или как я начал рисовать тор в блокноте)

Все возможные комбинации шапок — это 3ⁿ точек. Я представил это как n-мерный тор Z₃ⁿ. Каждая координата — цвет одного гнома (0, 1 или 2).

Рис. 1. Тор для трёх гномов. Цвет точки — цвет шапки первого, размер — сумма по модулю 3.
Рис. 1. Тор для трёх гномов. Цвет точки — цвет шапки первого, размер — сумма по модулю 3.

  • 3D-визуализация пространства состояний Z₃×Z₃×Z₃

  • Расслоение по сумме (mod 3)

  • Вероятностная поверхность выживания

Если нарисовать для n=3, получается 27 точек. И вот что странно: они сами собой разбиваются на три «слоя» по сумме цветов по модулю 3. Дракон, сам того не зная, создал расслоение. Я когда это заметил, даже засмеялся — ну надо же.

Как последний гном стал «передатчиком»

Идея простая, но гениальная (и старая как мир):

Последний гном считает сумму шапок впереди: S₁ = c₂ + c₃ + … + cₙ (mod 3) и называет цвет, соответствующий этой сумме.

Своя шапка у него при этом может не совпасть — вероятность ровно 1/3 (потому что полная сумма равномерна). Но зато он передаёт остальным важную информацию: «ребята, сумма впереди у меня вот такая».

Предпоследний слышит это, считает сумму шапок перед собой, вычитает — и узнаёт свою. Третий слышит уже два правильных ответа и тоже вычитает. И так до первого.

В итоге n−1 гномов спасены железно, последний — в лотерее.

Я когда проверял на бумаге для n=4, сначала не поверил, что так просто работает. А потом запустил код — и да, работает.

Рис. 2. Блок-схема спасительного алгоритма и формальное доказательство. Зелёные блоки — выживание, красный — риск. Синяя стрелка показывает цикл передачи информации.
Рис. 2. Блок-схема спасительного алгоритма и формальное доказательство. Зелёные блоки — выживание, красный — риск. Синяя стрелка показывает цикл передачи информации.

Топология и прочие «излишества», которые я всё-таки добавил

Потом я начал думать: а можно ли посмотреть на это как на тополога? Пространство — симплициальный комплекс, связные компоненты по сумме mod 3. Betti-числа получаются интересные (β₀ = 3, а дальше уже зависит от того, как считать).

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

Рис. 3. Симплициальный комплекс состояний (слева) и его гомологическая сложность (справа). Betti числа показывают, сколько «дыр» в нашем пространстве решений.
Рис. 3. Симплициальный комплекс состояний (слева) и его гомологическая сложность (справа). Betti числа показывают, сколько «дыр» в нашем пространстве решений.

Что нам дают Betti числа?

  • β0​=3 — три связных компоненты (по сумме mod 3)

  • β1​=2n — циклы зависимостей между гномами

  • β2​=n(n−1)/2 — двумерные «пузыри» возможностей

Энтропия и информация (Шеннон бы одобрил)

Начальная неопределённость — n·log₂(3) ≈ 1.585n бит. После первого ответа остаётся только 1.585 бит (сама сумма). То есть один гном передаёт ровно столько информации, сколько нужно, чтобы спасти всех остальных.

Я посчитал КПД: (n−1)/n. При больших n это почти 100 %. Красиво.

Спектральный анализ (да, я дошёл и до Фурье)

Взял функцию суммы цветов и применил дискретное преобразование Фурье. Пики на частотах 0, 1/3 и 2/3 — как отпечаток пальца задачи. Если бы цветов было 4, пики были бы на k/4.

Звучит пафосно, но на самом деле это просто показывает симметрию Z₃. Я сам удивился, когда увидел график.

Рис. 4. Спектральный анализ состояний. Пики на частотах k/3 показывают троичную симметрию задачи.
Рис. 4. Спектральный анализ состояний. Пики на частотах k/3 показывают троичную симметрию задачи.

Пики на частотах 0, 1/3, 2/3 — это не случайность! Они отражают циклическую симметрию Z₃. Если бы дракон выбрал 4 цвета, мы бы увидели пики на k/4.

Монте-Карло: проверил на компьютере (ну и остальные графики я как бы не от руки рисовал, привет модератору)

Запустил 10 000 симуляций (Python, numpy, случайные шапки).

Рис. 5. Результаты Монте-Карло симуляций. Верхний левый — распределение названных и реальных цветов. Верхний правый — сходимость к теоретической вероятности 1/3.
Рис. 5. Результаты Монте-Карло симуляций. Верхний левый — распределение названных и реальных цветов. Верхний правый — сходимость к теоретической вероятности 1/3.

Результаты получились такие:

  • эмпирическая вероятность для последнего — 0.3348 (теория 0.3333)

  • отклонение в пределах шума

Кривая сходимости красиво прижалась к 1/3. Закон больших чисел работает, как часы.

Корреляции между гномами

Формально цвета независимы, но после того, как сумма зафиксирована, появляется слабая отрицательная корреляция. Если знаешь все шапки кроме своей — можешь вычислить свою однозначно. Матрица взаимной информации это хорошо показывает. (нижний правый график Рис.5).

Эпилог (то, что я понял сам)

Задача учит простым вещам:

  • Иногда один должен пожертвовать собой, чтобы остальные выжили.

  • Информация дороже всего — один цвет (log₂(3) бит) спасает кучу жизней.

  • Математика может быть одновременно простой и безумно сложной, если её чуть-чуть «перекрутить».

  • И да, драконы действительно не любят алгебру.

Приложение: Сводка результатов

Таблица 1. Полная сводка математических результатов задачи о гномах.
Таблица 1. Полная сводка математических результатов задачи о гномах.

P.S.

Если ты гном и читаешь это перед драконом — просто суммируй шапки впереди по модулю 3 и называй результат. Остальные тебя не подведут.

А если ты математик — попробуй сам усложнить задачу дальше. Я дошёл до топологии и Фурье. Дальше уже, наверное, квантовая механика или теория категорий :-)