Выбор шкатулок
Задача
Султан выложил по кругу 6 внешне одинаковых шкатулок и сообщил двум своим мудрецам, что в четырех из них будут положены алмазы, а две останутся пустыми. Два мудреца должны будут по очереди забирать по одной шкатулке, при этом первый мудрец будет знать, где именно лежат алмазы, а второй — нет. Как им заранее договориться о своих действиях, чтобы забрать все алмазы и не взять ни одной пустой шкатулки? Как действовать мудрецам, если шкатулок 30 и в 20 из них лежат алмазы? А если шкатулок 10 и в 5 из них алмазы?
Подсказка
Сперва полезно разобраться, как действовать мудрецам в еще более простом случае: когда шкатулок всего три, а алмазов в них два. Именно к такому случаю хотелось бы свести сначала первый вопрос, а потом — и второй.
В третьем случае эта идея, к сожалению, не работает, потому что доля шкатулок с алмазами меньше 2/3. Однако 10 — это две пятерки. Подумайте, как бы вы решали задачу для пяти шкатулок, в которых есть три алмаза.
Решение
Для трех шкатулок по кругу две шкатулки с алмазами всегда стоят рядом. Значит, первый мудрец (знающий их расположение) может взять первую из них по часовой стрелке (то есть такую, за которой по часовой стрелке будет второй алмаз), а второй — следующую за взятой.
Теперь легко можно найти ответ на первый вопрос.
Если в шести шкатулках лежат 4 алмаза, то среди них (например, по принципу Дирихле) найдутся две соседних, причем такие две, что перед первой из них находится пустая шкатулка. Тогда первый мудрец берет первую такую шкатулку, а второй — другую. После этого второй мудрец понимает, в какой из шкатулок точно нет алмаза, и мысленно выкидывает ее, а на оставшихся трех шкатулках мудрецы повторяют ту же стратегию.
Во втором случае (всего 30 шкатулок, в 20 из них алмазы) работает аналогичная стратегия, поскольку после каждого хода доля шкатулок с алмазами (среди невзятых и невыкинутых мысленно) остается той же самой — 18 из 27, 16 из 24 и т. д., то есть всегда 2/3.
Для последнего вопроса (10 шкатулок, в 5 из них алмазы) так же действовать уже не получится, и стратегия должна быть сложнее (ее первый шаг фактически описан в подсказке). Так как три из пяти алмазов должен будет взять первый мудрец, то мы ищем стратегию, позволяющую второму мудрецу сделать два правильных хода. Разобьем круг из 10 шкатулок на две группы по 5 «через один», то есть на «четные места» и «нечетные места». Так как всего в них 5 алмазов, то в какой-то группе алмазов не менее трех.
Рассмотрим отдельно два варианта расположения алмазов по четностям — 4+1 (или 5+0) и 3+2.
В варианте «4+1» (или 5+0) первый мудрец делает оба первых хода в шкатулки одной и той же четности, причем так, чтобы второй всегда смог забрать следующую по часовой стрелке шкатулку из той же группы. После этого пятую шкатулку с алмазом заберет себе первый мудрец.
В варианте «3+2» сходить четырежды в одну четность уже никак не получится, поэтому второй ход первого мудреца будет в шкатулку другой четности, — и это будет сигналом для второго мудреца, что и ему нужно поменять четность выбираемой шкатулки. Заметим, что мы уже запланировали первый ответ второго мудреца в следующую по часовой стрелке шкатулку той же четности. Сможет ли он и второй раз ответить в следующую по часовой стрелке шкатулку? Оказывается, не всегда. Действительно, в трех шкатулках (из пяти) всегда найдутся «соседи» (тут это фактически означает «через одну»),а вот в паре шкатулок другой четности таких «соседей» может и не быть. Однако там всегда есть либо «соседи» (то есть шкатулки с разницей номеров 2), либо «несоседи» с разницей 4, а в тройке шкатулок обязательно будет и разница 2, и разница 4. Это соображение дает мудрецам работающую стратегию из двух ходов: на первом ходу второй мудрец должен выбирать шкатулку с номером «+2» (то есть через одну от взятой первым по часовой стрелке), а на втором ходу — шкатулку с номером «+4»! Чтобы это сработало, первый должен сперва проанализировать разницу номеров шкатулок с алмазами в той группе, где их два — и если там «+2», то сперва сходить туда, а если там «+4», то сперва сделать ход в другой пятерке.
Послесловие
Мы разобрали две простых и одну не очень простую задачу о поиске «протокола безошибочной передачи информации». Первый вопрос — о шести шкатулках (в немного другой формулировке) — предлагался девятиклассникам в 2018 году на муниципальном этапе ВсОШ (Всероссийской олимпиады школьников). Второй вопрос — о 30 шкатулках (тоже в иной фабуле) — был в конкурсе им. Савина журнала «Квант» для школьников 6–8 классов в 2019 году (автор — А. К. Ковальджи). Третий вопрос, как ни удивительно, придуман намного раньше автором этой статьи, но ни в каких олимпиадах и конкурсах использован не был.
Что еще известно об этом сюжете? Ясно, что если шкатулок без алмазов совсем мало, то мудрецы легко справятся. Доля 2/3 — не единственная, для которой они смогут забрать все шкатулки с алмазами. Например, если 98 шкатулок из 100 содержат алмазы, то возможны ровно две принципиально отличающиеся «картинки»: шкатулки без алмазов являются либо несоседними, либо соседними. В первом случае они делят круг на две части, и первым ходом «знающий» мудрец (назовем его Знайка) заберет алмаз из большей части, лежащий в шкатулке сразу после «дырки», тогда второй («Незнайка») сможет забрать следующий за ним алмаз, — а вторым ходом Знайка заберет алмаз, лежащий после второй дырки, и этим выдаст Незнайке всю нужную информацию. Во втором же случае Знайка снова начнет со следующего за «дыркой» алмаза и будет последовательно продолжать забирать следующие по часовой стрелке алмазы, сигнализируя, что «дырки» тут нет и бояться нечего. Собственно, и здесь тоже после второго хода Знайки вся информация у Незнайки уже есть.
А если шкатулок без алмазов много, а с алмазами — мало? Тогда, увы, выигрышной стратегии у мудрецов нет. Такая задача тоже уже встречалась в олимпиадах — в 2010 году на олимпиаде ЮМШ (авторы — М. Антипов и К. Кноп) предлагалось доказать, что если всего 12 из 37 шкатулок содержат алмазы, то мудрецы проигрывают...
Действительно, рассмотрим начальную ситуацию с точки зрения Незнайки. Любая работающая стратегия должна каждой шкатулке X, взятой Знайкой, сопоставить какую-то шкатулку F(X), которую сможет взять Незнайка. Но из 37 шкатулок всегда можно выбрать 12 так, что никакие две из них не образуют пару (X, F(X)) — и такая возможность немедленно приводит к противоречию: ведь если именно в эти 12 шкатулок положить алмазы, то у Знайки с Незнайкой не будет даже первого хода!
То, что в этой ситуации всегда можно выбрать 12 шкатулок, среди которых нет ни одной пары (X, F(X)), несложно объясняется на языке графов. Шкатулки будут вершинами графа, и для каждой пары (X, F(X)) проведем стрелку от X к F(X). Всего получится 37 стрелок. Так мы построим ориентированный граф на \(3\cdot12+1=37\) вершинах с исходящей степенью 1. Разобьем «стрелочки» на циклы, в каждом цикле будем брать вершины через одну, — ясно, что все выбранные вершины будут независимыми. Так как в циклах длины \(2k\) и \(2k+1\) мы сможем выбрать ровно \(k\) вершин, то доля выбранных вершин будет меньше всего для коротких нечетных циклов — то есть циклов длины 3, из которых мы можем брать всего одну вершину. Поскольку всего вершин 37 и из каждого цикла мы берем не меньше трети вершин, то и всего будет выбрано не меньше трети вершин, то есть не меньше 12.
С другой стороны, в пределе доля безалмазных шкатулок может быть и меньше половины — автору кажется, что она стремится к 1/3 при количестве шкатулок, стремящемся к бесконечности.
Задачи о передаче секретной информации «поверх» какой-то чужой информации, разумеется, не новы и относятся к одной из ветвей криптографии. Некоторые из них уже давно циркулируют в математическом сообществе как фольклорные головоломки. Например, именно такова задача о 15 битах и шпионке из книги Питера Уинклера «Математические головоломки. Коллекция гурмана», вот она в слегка отредактированной формулировке:
Во время перерыва на профилактику радиостанция ежедневно транслирует короткое сообщение длиной 15 битов. Шпионка получила доступ к этим сообщениям — это ее единственный канал общения с центром. Она не знает, как выбираются биты для каждого сообщения, но у нее есть возможность подменить любой из них (причем только один), то есть поменять его с 0 на 1 или наоборот. Какое количество битов полезной информации она может передавать в центр ежедневно?
Уинклер пишет, что узнал задачу от венгерского математика Ласло Ловаса, но ясно, что и Ловас тоже ее от кого-то узнал...
Другая версия этой же задачи — о шахматной доске:
Султан желает проверить, насколько разумны два его мудреца. Для этого он выбирает клетку шахматной доски и показывает ее первому мудрецу. На каждой клетке доски либо лежит камешек, либо не лежит. Мудрецу разрешается убрать с доски один камешек или положить на пустую клетку один камешек. После этого второй мудрец должен назвать ту клетку, которую выбрал султан. Как мудрецам договориться, чтобы доказать султану свою мудрость?
Понятно ли, почему эти две задачи фактически одинаковы (изоморфны)?
Решение задачи о шпионке
Поскольку шпионка может произвести всего 16 действий (или изменить какой-то бит, или ничего не менять), то она сможет передавать четыре бита информации — и не больше. Но как именно это реализовать? Присвоим каждому разряду из сообщения радиостанции четырехбитовый двоичный код, соответствующий его номеру (то есть закодируем последовательные разряды сообщения радиостанции от 0001 до 1111). Далее можно сосчитать сумму всех единиц в сообщении (или, что то же самое, четность их количества) по всем разрядам, в i-м бите которых стоит 0.
Эта сумма (ее еще называют ним-суммой, или нимбером) — какое-то четырехбитовое двоичное число от 0000 до 1111. Чтобы передать именно это число, шпионка не должна менять в сообщении ничего. Чтобы передать какое угодно другое число, она должна поменять какие-то двоичные разряды в побитовых суммах. Например, если ним-сумма равна 0101, а шпионка хочет передать ним-сумму 1100, ей надо поменять 0 на 1 в старшем разряде ним-суммы и 1 на 0 в младшем. Но это значит, что ей достаточно внести изменение в 1001-й символ строки — то есть поменять этот элемент (не важно, 0 на 1 или 1 на 0), — именно это даст эффект в нужных битах ним-суммы.
Для шахматной доски все делается ровно так же, только ним-сумма будет шестибитовой, а не четырехбитовой.
Еще один пример подобной задачи — задача про фокус, впервые предложенная на Всероссийской олимпиаде в 2007 году (авторы — О. Леонтьева и К. Кноп):
Фокусник с помощником собираются показать такой фокус. Зритель пишет на доске последовательность из N цифр. Помощник фокусника закрывает две соседних цифры черным кружочком. Затем входит фокусник. Его задача — отгадать обе закрытые цифры и порядок, в котором они расположены. При каком наименьшем N фокусник может договориться с помощником так, чтобы фокус гарантированно удался?
Решение задачи про фокус
Ответ: при \(N=101\).
Решение. Предположим, что при каком-то значении \(N\) фокус удастся. Тогда по каждому варианту последовательности с двумя закрытыми цифрами (пусть их количество равно \(k_1\)) фокусник может восстановить исходную. Значит, каждой последовательности с двумя закрытыми цифрами фокусник однозначно может поставить в соответствие восстановленную последовательность из \(N\) цифр (пусть их количество равно \(k_2\)). Следовательно, \(k_1\ge k_2\). Отметим, что \(k_1=(N-1)10^{N-2}\) (есть \(N-1\) вариант вычеркнуть две цифры, а на остальные \(N-2\) позиции есть по 10 вариантов на каждую). А \(k_2=10^N\). Значит, \(N-1\ge100\), то есть \(N\ge101\).
Покажем, как выполнить фокус при \(N=101\). Пусть сумма всех цифр на нечетных позициях имеет остаток \(s\) от деления на 10, а сумма всех цифр на четных позициях имеет остаток \(t\) от деления на 10 (позиции нумеруются слева направо числами от 0 до 100). Положим \(p=10s+t\). Пусть помощник закроет цифры, стоящие на позициях \(p\) и \(p+1\). Увидев, какие цифры закрыты, фокусник определит \(p\), а следовательно, определит \(s\) и \(t\). Отметим, что одна закрытая цифра всегда стоит на нечетной позиции, а другая — на четной. Вычислив сумму открытых цифр на нечетных позициях и зная \(s\), фокусник определит закрытую цифру, стоящую на нечетной позиции. Аналогично определяется закрытая цифра, стоящая на четной позиции.
В той же книге Уинклера есть и другие задачи об интересных криптографических протоколах. Новизна версий, которые мы обсуждали выше, связана разве что с тем, что в них передача информации от одного мудреца к другому делается не целиком и сразу, а пошагово — один шаг, потом второй, и так далее до конца.
-
Я предвижу сетования фокусника на десятичную систему!
Слишком цифр много, фокус получается муторный и тоскливый:
это ж сколько нужно ждать, пока вызванный из зала зритель накалякает сто одну цифру!
И он сам, и остальные зрители в зале да и сами фокусник с ассистентом повывихивают челюсти зевотой.
То ли дело двоичная система!
С нею фокус будет стремительным и броским!
Пять цифр - и вуаля!
И народ валом повалит на следующие представления.
