Мудрецы, колпаки и арифметика конечных полей

Мудрецы, колпаки и арифметика конечных полей

С.ГРИБОК

Испытание 1. Два из трех. О двоичных наборах, кубах и шарах

Давным-давно правил в Персии царь Шахрияр. Целыми днями царь пировал, охотился и развлекался, устраивая жестокие испытания для своих придворных. В то время как царь проводил время в праздности, решением всех запутанных государственных дел и управлением страной занимался совет придворных мудрецов. Однажды царь решил проверить, так ли уж умны его придворные мудрецы. Он приказал позвать трех мудрецов и объявил условия испытания, которое ожидает их завтра. Каждому мудрецу на голову наденут колпак белого или черного цвета. Каждый сможет видеть чужие колпаки, но не будет знать, какого цвета его колпак. Какой именно колпак надеть на каждого мудреца, решит палач, трижды подбросив монету, одна сторона которой окрашена в белый цвет, а другая – в черный. Затем каждому мудрецу дадут перо и лист пергамента, на котором он напишет, какого цвета его колпак. Если хотя бы двое мудрецов ответят правильно, всех наградят, если же хотя бы двое ошибутся, всех мудрецов казнят. Подавать друг другу какие-либо знаки во время испытания запрещено. За ночь перед испытанием у мудрецов есть возможность договориться и выработать единую стратегию. Как следует действовать мудрецам, чтобы максимизировать шансы остаться в живых? Докажем, что не существует способа, позволяющего сделать вероятность выигрыша мудрецов больше чем 3 4.

DOI: https://doi.org/10.4213/kvant20190402

Пусть испытание повторяется много раз. Пусть мудрецам удалось разработать метод, позволяющий двум мудрецам из трех угадывать цвета своих колпаков в среднем чаще, чем в трех играх из четырех. Таким образом, из 12 ответов мудрецов, прозвучавших в течение четырех игр, в среднем более 6 ответов будут верными ( 6 3 ˜ 2 ). Но это невозможно, так как каждый мудрец угадывает цвет своего колпака в одном случае из двух, а значит, из 12 ответов в среднем ровно 6 ответов верны. Всего есть 8 различных вариантов распределения колпаков между тремя мудрецами. Вероятность выигрыша 3 4 означает, что мудрецы побеждают в шести вариантах, а проигрывают в двух вариантах из восьми. Попробуем построить такую стратегию мудрецов, которая позволит им выигрывать в шести случаях из восьми. Для удобства записи наборов колпаков будем использовать цифру 0 для обозначения белого колпака, а цифру 1 для обозначения черного колпака. Например, запись 001 будет означать, что первым двум мудрецам достались белые колпаки, а третий мудрец получил черный колпак. Выберем два «смертельных» набора колпаков, которые мудрецы не смогут угадать. Например, пусть смертельными будут наборы 000 и 111. Мы хотим, чтобы на всех остальных наборах мудрецы смогли выиграть. Как этого добиться? Прежде всего заметим, что для любого не смертельного набора колпаков один из мудрецов видит на соседях колпаки одного и того же цвета. Стратегия этого мудреца ясна: если видишь на соседях два колпака одного цвета, называй другой цвет. Оче-

6

КВАНТ 2019/№4

видно, для любого не смертельного набора эта стратегия работает и гарантированно позволит мудрецу угадать цвет своего колпака. Займемся оставшимися двумя мудрецами, каждый из которых видит на соседях колпаки разных цветов. Чтобы выиграть, достаточно, чтобы хотя бы один из этих мудрецов назвал цвет своего колпака правильно. Заметим также, что их собственные колпаки одного и того же цвета. Значит, если один из мудрецов назовет белый цвет, а другой – черный, то один обязательно угадает. Но как мудрецы узнают, какой цвет называть, если они оба видят одну и ту же картину – на соседях колпаки разных цветов? Дело в том, что если присмотреться внимательнее, мы заметим: в том, что видят эти два мудреца, есть некоторые различия. Пусть, например, мудрецы встали в круг. Тогда один из двух мудрецов видит слева белый колпак, а справа – черный. Другой мудрец видит иную картину: слева черный колпак, а справа – белый. Теперь легко придумать правило, которое позволит одному из этих мудрецов угадать цвет своего колпака: если видишь на соседях колпаки разных цветов, называй тот цвет, который видишь справа (заметим, что также годится и «зеркально-симметричное» правило: если видишь на соседях колпаки разных цветов, то называй тот цвет, который видишь слева). Итак, задача решена, но не будем торопиться. Во-первых, подумаем, нельзя ли упростить правила, которым должны следовать мудрецы. Нетрудно догадаться, что два найденных нами правила можно переформулировать в виде одного простого правила: называй НЕ тот цвет, который видишь на соседе слева. Во-вторых, построим геометрическую интерпретацию задачи о трех колпаках. Удобно представить множество вариантов распределения колпаков в виде куба (рис.1). Каждый набор колпаков соответствует одной из вершин куба. Если два набора колпаков отличаются лишь цветом одного колпака (такие наборы называются

Рис. 1

соседними), они расположены в вершинах, соединенных ребром. Достроим теперь два шара, центры которых находятся в смертельных точках 000 и 111, а радиусы равны ребру куба. Каждый шар покрывает четыре точки куба. Каждая точка куба либо находится на поверхности, либо в центре одного из шаров. В таких случаях говорят, что построено «покрытие куба непересекающимися шарами». Если точка оказалась в центре шара, мудрецы не угадают цвета своих колпаков, если же точка лежит на поверхности шара, большинство мудрецов назовут свои цвета правильно.

Испытание 2. Четыре из семи. О многочленах и кодовых множествах

На следующий день к царю привели семерых мудрецов. Правитель объявил, что сегодня состоится еще одно испытание. Правила те же, что и вчера: каждому мудрецу на голову наденут колпак белого либо черного цвета, после чего каждый мудрец должен записать, какого цвета по его мнению колпак на его голове. Если хотя бы четверо мудрецов ответят правильно, всех наградят, если же хотя бы четверо ошибутся, всех казнят. Как следует действовать мудрецам, чтобы и на этот раз свести вероятность казни к минимуму? Опять начнем с нижней оценки вероятности казни. Докажем, что не существует

7

МУДРЕЦЫ,

КОЛПАКИ

И

АРИФМЕТИКА

способа, позволяющего сделать вероятность выигрыша больше чем 7 8. Доказательство такое же, как и в первой задаче, с точностью до замены чисел. Пусть мудрецам удалось разработать метод, позволяющий четырем мудрецам из семи угадывать цвета своих колпаков в среднем чаще, чем в семи играх из восьми. Таким образом, из 56 ответов мудрецов, прозвучавших в течение восьми игр, в среднем более 28 ответов будут верными ( 28 7 ˜ 4 ). Но это невозможно, так как каждый мудрец угадывает цвет своего колпака в одном случае из двух, а значит, из 56 ответов в среднем ровно 28 ответов верны. Всего есть 128 различных вариантов распределения колпаков между семью мудрецами. Вероятность выигрыша 7 8 означает, что мудрецы побеждают в 112 вариантах, а проигрывают в 16 вариантах из 128. По аналогии с первой задачей теперь надо как-то выбрать 16 смертельных наборов. Но как это сделать? В предыдущей задаче все наборы из трех колпаков мы расставили по вершинам куба. Теперь колпаков семь, а значит, множество наборов соответствует вершинам семимерного гиперкуба. Представить эту фигуру сложно, однако это не мешает нам порассуждать о ее свойствах. Заметим, что так как мудрецов семеро, то для каждого набора колпаков существует семь соседних наборов, следовательно, каждый 7-мерный шар единичного радиуса с центром в вершине N-мерного куба покрывает ровно 8 точек куба. Поскольку 128 16 ˜ 8, то теоретически для покрытия всех 128 вершин 7-мерного куба как раз должно хватить шестнадцати непересекающихся 7-мерных шаров, в центре каждого из которых мы поместим смертельный набор. Вот только как это сделать на практике? Будем называть расстоянием между двумя наборами число позиций, в которых эти наборы отличаются. Расстояние между соседними наборами равно единице. Теперь сформулируем свойства множества смертельных наборов, которое мы хотим построить.

КОНЕЧНЫХ

ПОЛЕЙ

1. Всего в множестве 16 наборов. 2) Расстояние между любыми двумя наборами не меньше трех (чтобы шары, в центрах которых находятся смертельные наборы, не пересекались). 3) Циклический сдвиг смертельного набора также является смертельным набором (иначе разным мудрецам придется использовать различные стратегии). Интуитивно ясно, что смертельные наборы должны быть равномерно распределены на множестве всех возможных наборов. Можно попробовать представить каждый набор колпаков как двоичную запись некоторого целого числа от 0 до 127, а множество смертельных наборов – как элементы некоторой арифметической прогрессии, однако традиционные арифметические операции плохо подходят для обеспечения нужных нам свойств 2 и 3. Так как традиционная арифметика нам не подходит, воспользуемся «нетрадиционной» арифметикой, а именно, так называемой арифметикой многочленов над полем {0,1}. Прежде всего определим операцию сложения двух наборов колпаков. Сумма двух наборов длины n – это набор длины n, каждый элемент которого равен сумме по модулю 2 соответствующих элементов исходных наборов. Напомним правила сложения по модулю 2: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0. Пример: 00110101 + 11110000 = 11000101. Чтобы определить операции умножения и деления наборов колпаков, удобно записывать наборы в виде многочленов. Набор колпаков $v_{0}, v_{1}, v_{2},^{…}, v n_{1}$ можно записать в виде многочлена от переменной $х:_{0}^{v} v_{1}$ ˜ $x_{2}^{v}$ ˜ $x^{2} …^{v} n_{1}$ ˜ $x^{n} 1$. Таким образом, множество наборов длины n эквивалентно множеству многочленов, степени которых не превышают n – 1. Теперь определим произведение двух наборов как набор, соответствующий мно-