Волк и три поросёнка

Попробуйте разобраться с упрощением этой задачи до двух поросят и трёх цветов. Какой может быть хорошая стратегия для поросят? Если один из них будет всегда молчать, а второй будет всегда пытаться угадать цвет своей повязки, то им удастся спастись с вероятностью 1/3. Можно ли это улучшить?

Да, для двух поросят и трёх цветов улучшение возможно. Перенумеруем для краткости цвета: 1, 2 и 3. Тогда всего имеется девять случаев. «Стратегия спасения», позволяющая поросятам выжить в четырёх из них (то есть с вероятностью 4/9 > 1/3), может быть сформулирована так: если видишь повязку цвета 2 или 3, то говори, что на тебе повязка цвета 1, а иначе молчи. Выигрышными при этом являются случаи (1, 2), (1, 3), (2, 1) и (3, 1). В случаях (2, 3), (2, 2), (3, 2) и (3, 3) оба поросёнка ошибаются, а в случае (1, 1) оба погибают из-за молчания.

А можно ли добиться еще большего (по-прежнему, для двух поросят и трёх цветов)? Оказывается, нет. Чтобы объяснить это, изобразим произвольную стратегию поросят в виде таблички 3×3. А именно, пусть строки таблицы соответствуют трем возможным цветам повязки у первого поросёнка, а столбцы — цветам второго. Иными словами, первый поросёнок знает столбец, соответствующий данному случаю (паре цветов повязок), а второй — строку. Если для какого-то из столбцов наша стратегия велит (возможно, с привлечением случайности, например бросания монетки) называть свой цвет первому поросёнку, то такой столбец назовём отмеченным. Аналогично определим и отмеченную строку. В каждом отмеченном ряду только одна клетка может соответствовать выигрышу (спасению поросят), а две остальных — проигрышу (ошибке). Направим стрелки от выигрышной клетки к каждой из этих двух проигрышных. Из каждой выигрышной клетки мы направили две стрелки. Если W — количество выигрышных клеток, то 2W — число нарисованных нами стрелок. Поскольку в каждую проигрышную клетку входит не более двух стрелок (не более одной горизонтальной и одной вертикальной), то число нарисованных стрелок не больше удвоенного числа проигрышных клеток 2(9–W). Из неравенства 2W ≤ 2(9–W) получаем, что 2W ≤ 9, откуда W ≤ 4. Пример стратегии, спасающей поросят в четырех случаях из девяти, мы уже привели.

Случай двух цветов (и трех поросят) разбирается практически так же, как и разобранный в подсказках «плоский» случай двух поросят. Только игровым полем здесь будет уже не квадратная табличка, а кубическая — 2×2×2 (а для трех цветов — 3×3×3). Чтобы понять, какой должна быть оптимальная стратегия поросят, сначала разберёмся с тем, к чему они должны стремиться — то есть каков идеальный для них случай.

Итак, займёмся поиском того, что математики называют «верхними оценками».

а) M = 2. Как и в подсказке, выделим отмеченные ряды, а в них — выигрышные клетки, из которых направим стрелки во все остальные (невыигрышные). Тогда из каждой выигрышной клетки ведёт ровно одна стрелка, а в каждую невыигрышную входит не более трёх стрелок (не более чем по одной с каждого направления). Если W₂ — число выигрышных клеток, то из подсчёта стрелок получаем неравенство W₂ ≤ 3(8 – W₂), из которого следует W₂ ≤ 6.

б) M = 3. Здесь из каждой выигрышной клетки выходят две стрелки, поэтому аналогичное неравенство имеет вид 2W₃ ≤ 3(27 – W₃), откуда W₃ ≤ 16.

Теперь, когда какие-то ориентиры найдены, мы можем опереться на них и сконструировать оптимальные решения для поросят.

а) M = 2. Чтобы суметь получить 6 выигрышных клеток (которые нам разрешает получить верхняя оценка), мы должны добиться того, чтобы на каждую невыигрышную клетку указывали ровно три стрелки. Это значит, что она вместе с тремя соседними клетками должна образовывать «ёжик» из четырёх клеток, а весь куб 2×2×2 должен быть составлен из двух таких «ёжиков». Этого несложно достичь, если центральными клетками двух «ёжиков» сделать противоположные вершины куба. Таким образом, невыигрышные позиции — это клетки (0, 0, 0) и (1, 1, 1), а выигрышные — все остальные. При этом стрелки из каждой клетки куба должны быть направлены к ближайшей из двух клеток (0, 0, 0) и (1, 1, 1). Например, стрелка из (0, 1, 0) должна вести в (0, 0, 0). Для поросят это означает, что в клетке (0, 1, 0) называть свой цвет (говорить «1») должен тот поросёнок, у которого он отличается от двух остальных цветов. Таким образом, формулировка оптимальной стратегии на «языке поросят» звучит примерно так: если видишь у двух остальных повязки одного цвета — называй другой цвет, иначе помалкивай. Итого мы получили ответ: 6/8 = 3/4.

б) M = 3. А вот тут — неприятный сюрприз: достичь результата, который был бы равен верхней оценке, не получается. Лучшее, что удаётся сделать, — это 15 выигрышных клеток. (Увы, такая ситуация очень типична для любых комбинаторно-алгоритмических проблем: алгоритм (нижняя оценка) даёт худший результат, чем тот, на который позволяла рассчитывать верхняя оценка. Что делают в таких случаях? Внимательно анализируют причины расхождения алгоритма с оценкой — чаще всего это помогает либо понять, как можно улучшить алгоритмическую часть, либо придумать уточнение верхней оценки.) При этом стратегия для поросят, гарантирующая выигрыш в 15 случаях из 27, может быть описана, например, так: если видишь, что у остальных двух поросят нет повязок первого цвета, — говори «1». Если у обоих поросят видишь повязки первого цвета — говори «2». Выигрывают при этом все клетки, в которых ровно одна координата равна 1 (при этом для двух остальных есть 4 возможности, поэтому всего таких клеток 3×4 = 12) и три клетки (1, 1, 2), (1, 2, 1) и (2, 1, 1).

Попробуем понять, почему мы не достигли заветного рубежа «16». Допустим, что нам удалось построить алгоритм с 16 выигрышными клетками. Это означает, что в каком-то одном из трёх направлений («длина», «высота», «ширина») отмеченных рядов не менее 6 (если бы в каждом направлении было 5 или меньше, то всего было бы не более 15). В каждом из таких рядов — по две невыигрышных клетки, и поскольку все эти ряды идут вдоль одного направления, то все эти 12 клеток различны. Но тогда получается противоречие: если 12 клеток невыигрышны, то выигрышных не может быть больше, чем 27 – 12 = 15. Ура! Мы сумели улучшить оценку, а значит, наш алгоритм даёт максимально возможное количество выигрышных клеток. Ответ: 15/27 = 5/9.

Задача о повязках двух цветов, пожалуй, наиболее известна и ныне считается чуть ли не классической задачей, иллюстрирующей применение совершенных кодов Хемминга. Хотя ее появление можно установить с очень большой точностью — впервые она была рассмотрена в кандидатской диссертации Тодда Эберта в 1998 году.

Приведенная здесь мной формулировка с волком и поросятами была придумана, по-видимому, замечательным математиком из Новосибирска Дмитрием Германовичем фон дер Флаассом. Я взял и формулировку, и основные идеи решения этой задачи из его, ныне мемориального, «Живого журнала» flaass.livejournal.com. Впрочем, Дмитрий не остановился на почти тривиальном случае трёх поросят, а перешёл к значительно менее простому 7-мерному случаю (у него это названо «задачей о Белоснежке и семи гномах») и отметил, что этот результат допускает обобщение на любое число поросят вида 2^k – 1.

Позволю себе просто процитировать Д. Г. фон дер Флаасса:

Надо разбить весь 7-мерный куб на «ёжики» — пучки из 7 стрелок, выходящих из плохой вершины. Ёжиков будет 128/(7 + 1) = 16, их центры образуют совершенный код с расстоянием 3 — то есть расстояния между центрами не меньше 3 (а то бы ёжики пересекались), и каждая вершина — либо центр, либо находится рядом с каким-то центром (а то бы не всё покрылось).

Такие коды существуют в любой размерности n = 2^k – 1, в частности, для n = 7 = 2³ – 1. Очевидно, что в других размерностях совершенных кодов быть не может: 2ⁿ не делится на (n + 1).

Как сформулировать «правило для гномов»? [...] Пусть каждому гному выдан номер (от 1 до 7), записанный в двоичной системе: 001, 010, ..., 111. Гном считает побитовую сумму всех номеров с чёрными шапочками. Если эта сумма равна 0, гном кричит «чёрная». Если эта сумма равна своему номеру, гном кричит «белая». Иначе — помалкивает. Собственно, это и есть определение кода Хемминга. Оно обобщается на любое n = 2^k – 1.

Собственно, да, всё именно так.

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

Три поросёнка, повязки четырёх цветов. Всё та же оценка числа стрелок даёт неравенство 3W₄ ≤ 3(4³ – W₄), откуда W₄ ≤ 192/6 = 32. Как и для трёх цветов, равенство здесь не достигается. Более аккуратная оценка показывает, что ни в каком из трёх направлений не может быть более 10 отмеченных рядов, поэтому общее количество выигрышных клеток не более 30 (то есть вероятность выигрыша 30/64). Пример с 30 клетками строится аналогично тому, как выше был построен пример с 15 клетками для трёх цветов: «если видишь, что ни у кого из двух поросят нет повязки первого цвета, то говори 1. Если у обоих поросят повязки первого цвета, говори 2. Иначе молчи».

Три поросёнка, повязки M цветов. Аналогичный пример и аналогичная оценка, результат 3 + 3(M – 1)².

Четыре поросёнка, повязки трёх цветов. Лучший известный автору результат — 48/81. Оптимальность этого результата пока не доказана.

«Демократичный» Волк. Представьте себе, что Волк готов простить трём поросятам одну ошибку в том случае, если большинство (то есть оба остальных) назвали свой цвет правильно. Увеличивает ли это шансы поросят?

«Злобный» Волк. В этой версии Волк запрещает поросятам молчать. Ясно, что спастись теперь намного труднее. Каковы шансы при оптимальной стратегии?