Что у меня на лбу?

Подумайте, какими были бы числа на трех бумажках, если бы число 60 было опознано сразу же — первой репликой Веры? А если не сразу, а второй репликой (которую произнесла Надя)?

Разберитесь еще с такой версией задачи: в третьей реплике Люба заявила, что у нее на лбу число 60. Какие числа могли быть написаны у Нади и Веры?

Будем называть каждую из реплик ходом, а те ходы, в которых игрок не может опознать своего числа для краткости будем называть пасом. Ясно, что каждый игрок делает ход, исходя не только из тех бумажек, которые он видит (они с самого начала игры не меняются), но и из информации о предыдущих пасах других игроков. Самая важная и интересная часть этой задачи — научиться обрабатывать эту информацию.

Когда первый же ход может быть угадыванием числа, а не пасом? В самом начале игрок знает только то, что на его бумажке написано натуральное число, равное либо сумме двух других натуральных чисел, либо разности между большим и меньшим из чисел, которые он видит. Сумма x + y никогда не равна x − y (так как y > 0), поэтому у него почти всегда есть две возможности, и выбрать из них одну невозможно. Почему «почти всегда»? Потому что если x − y = 0, то эта возможность отпадает. Игрок, который видит на остальных два одинаковых числа, сразу понимает, что на нем не может быть разность, так как 0 не является натуральным числом! Таким образом, ответ на вопрос из первой подсказки такой: если Вера смогла угадать первым ходом, то и у Любы, и у Нади написано 30.

Перейдем к разбору того, какая информация есть у Нади на втором ходу игры. Конечно, она тоже смогла бы угадать свое число, если бы видела у сестер два одинаковых числа. То есть, когда она видит на них 30 и 30, то она тоже знает, что на ней самой число 60. Но, кроме этого, она еще знает, что первым ходом Веры был «пас», и это та информация, которой у Веры не было! Разберемся аккуратнее: Надя знает, что Вера видела, что на Наде и Любе числа разные. Это знание позволит Наде дополнительно исключить одну возможность из двух (и узнать свое число) в том случае, если эта возможность такова: на Вере число 2x, а на Наде и Любе — числа x. То есть если Надя действительно видит на Вере число, вдвое большее, чем число на Любе, то она может сразу сказать, что на ней самой — не число, равное числу Любы, а сумма двух видимых ею чисел, то есть втрое большее число! Иначе говоря, она сможет «опознать» число 60 в том случае, если видит на сестрах 20 (на Любе) и 40 (на Вере).

Подведем промежуточный итог. Угадывание первым ходом возможно только в ситуации 1.1 — когда тройка чисел (x, x, 2x), а угадывание вторым ходом означает одну из двух ситуаций: 2.1 = 1.1 — (x, x, 2x); 2.2 — (x,2x,3x). Способ записи троек чисел в скобках здесь и далее до конца решения будет таким: на последнем месте пишется число, равное сумме двух других, перед ним указано число у сестры, делавшей предыдущий ход, а первым стоит число той из сестер, чей ход был на два хода раньше. При этом значение x мы определим так, чтобы угаданное число оказалось равным 60.

Перейдем к вопросу из второй подсказки, то есть разберем информацию, которой владеет Люба к третьему ходу. Ясно, что Люба сможет угадать свое число в тех же случаях, когда его могла бы угадать Надя предыдущим ходом, то есть в ситуациях 3.1 = 1.1 — (x, x, 2x) и 3.2 = 2.2 — (x, 2x, 3x). При этом она фактически повторяет все рассуждения Нади и игнорирует самый первый ход Веры. Но у нее есть и новая информация: так как ни Вера, ни Надя не смогли угадать свое число, то тройка чисел на лбах сестер не совпадает ни с (2x, x, x), ни с (x, 2x, x), ни с (2x, 3x, x). Это значит, что если Люба видит (2x, x, ?), то она понимает, что на ней число 3x, а если она видит (2x, 3x, ?), то понимает, что на ней не разность этих чисел (равная x), а их сумма 5x. Таким образом, к списку «выигрышей» Любы добавляются ситуации 3.3 — (2x, x, 3x) и 3.4 — (2x, 3x, 5x). В каких из четырех ситуаций 3.1–3.4 Люба может опознать число 60? Да во всех! Каждая из ситуаций соответствует своему варианту: (30, 30, 60), (20, 40, 60), (40, 20, 60) и (24, 36, 60).

Продолжим. Начиная с четвертого хода, добавляется важная тонкость: если число можно было бы угадать предыдущим ходом, то это было бы сделано. Иначе говоря, на четвертом и последующих ходах мы не должны сохранять в качестве «выигрышей» те ситуации, которые были выигрышами на три хода раньше.

Четвертый ход (второй ход Веры): выигрышами являются повторения предыдущих ситуаций, то есть 4.1 — (x, 2x, 3x), 4.2 — (2x, x, 3x) и 4.3 — (2x, 3x, 5x). Выигрышем больше не является ситуация (x, x, 2x), которая была выигрышем еще на первом ходу Веры. Кроме этого, добавляются новые выигрыши, основанные на том, что Вера понимает значение предыдущих «пасов» Нади и Любы, то есть понимает, что ситуация не совпадает ни с одной из тех, которые были бы выигрышами 2.2, 3.3 и 3.4 для Нади и Любы. Это означает, что в ситуации (x, 3x, ?) Вера уже поймет, что на ней сумма 4x: 4.4 — (x, 3x, 4x), и аналогично для случая (3x, 5x, ?) придет к 4.5 — (3x, 5x, 8x). Мы получили пять разных выигрышей для четвертого хода.

Пятый ход (второй ход Нади): у нее есть выигрыши 5.1 — (2x, x, 3x), 5.2 — (2x, 3x, 5x), 5.3 — (x, 3x, 4x), 5.4 — (3x, 5x, 8x), аналогичные выигрышам четвертого хода, но нет того выигрыша (x, 2x, 3x), который был выигрышем еще на втором ходе. А теперь — новая информация: Надя анализирует предыдущие «пасы» Любы и Веры и понимает, что в ситуациях (3x, x, ?),(3x, 2x, ?), (5x, 2x, ?), (2x, 3x, ?), (x, 3x, ?), (3x, 5x, ?), (3x, 4x, ?), (5x, 8x, ?), у нее не может быть разность тех чисел, которые она видит на сестрах (иначе бы те опознали свои числа на предыдущих ходах). Следовательно, у Нади может быть только сумма. Это добавляет к списку выигрышей Нади ситуации 5.5–5.9: (3x, x, 4x), (3x, 2x, 5x), (5x, 2x, 7x), (3x, 4x, 7x),(5x, 8x, 13x).

Фактически мы уже проделали все рассуждения, которые будут работать для общего случая. Выигрышами на ходу под номером N + 3 являются все те ситуации, которые были выигрышами на ходу N + 2, но не были выигрышами на предыдущем ходу N этой же сестры; кроме этого, появляются новые выигрышные ситуации, основанные на информации о том, что предыдущими (последними; более ранние ходы не имеет смысла исследовать, потому что они уже учтены в предыдущих выигрышах) ходами сестры не смогли угадать свои числа.

Так, для шестого хода (второго хода Любы) из пятого хода переносятся выигрыши 6.1–6.7 (x, 3x, 4x), (3x, 5x, 8x), (3x, x, 4x), (3x, 2x, 5x), (5x, 2x, 7x), (3x, 4x, 7x), (5x, 8x, 13x). А анализ ситуаций (4x, x, ?), (8x, 3x, ?), (x, 4x, ?), (2x, 5x, ?), (2x, 7x, ?), (4x, 7x, ?) и (8x, 13x, ?), в которых могли бы не пасовать сестры предыдущими ходами, приводит к нахождению новых выигрышных ситуаций 6.8–6.14: (4x, x, 5x), (8x, 3x, 11x), (x, 4x, 5x), (2x, 5x, 7x), (2x, 7x, 9x), (4x, 7x, 11x) и (8x, 13x, 21x). Осталось только посмотреть внимательно на список 6.1–6.14 и найти в нем те варианты, в которых число Любы может быть равно 60. Очевидно, что это 6.1 — (15, 45, 60), 6.3 — (45, 15, 60), 6.4 — (36, 24, 60), 6.8 — (48, 12, 60) и 6.10 — (12, 48, 60) — всего пять вариантов.

Задача о трех шляпах с числами впервые появилась в начале 2000-х годов в журнале Sunday Times Magazine, а затем оттуда перекочевала в разные сборники головоломок. Подробное ее решение на основе стратегии «укорачивающейся цепочки» было предложено в 2007 году Брайаном Бенсоном и Янг Вангом. Ниже при описании общего подхода я в основном следую идеям из их статьи.

В решении мы показали, как решать задачу «что можно получить за малое число ходов», причем для любого «озвученного» игроком числа. Фактически мы исследовали задачу с конца. Однако совершенно очевидно, что, скажем, полностью рассмотреть все варианты, которые могут быть получены к 15-му ходу, уже нереально. Хотелось бы придумать другой подход — вместо перебора всех троек, которые могут получиться на 15-м ходу, хочется научиться перебирать все варианты с заданным числом (60) и для каждого из них найти длину кратчайшего решения. Именно этим мы сейчас и займемся.

Но сначала давайте разберем более известную (и намного более простую) задачу о двух шляпах:

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

Эта задача отличается от наших «трех шляп» не только количеством играющих, но и явным разрешением использовать совместно выработанную стратегию. Впрочем, как мы ниже покажем, это различие не очень существенно.

Задачу о двух шляпах обычно решают с помощью метода математической индукции, однако я покажу ее решение с помощью «укорачивающейся цепочки». Каждый из игроков строит цепочку вариантов, начинающуюся с пары (1, 2) и заканчивающуюся парой (N, N + 1), где N — число, которое он видит у напарника. Пусть, например, у игрока A на лбу написано число 4, а у игрока B — число 5. Тогда цепочки у игроков будут такими:
A: (1, 2)(2, 3)(3, 4)(4, 5)(5, 6),
B: (1, 2)(2, 3)(3, 4)(4, 5).

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

Таким образом, игра в нашем примере будет происходить так:
A: (1, 2)(2, 3)(3, 4)(4, 5)(5, 6) — «Пас»;
B: (1, 2)(2, 3)(3, 4)(4, 5) — «Пас»;
A: (2, 3)(3, 4)(4, 5)(5, 6) — «Пас»;
B: (2, 3)(3, 4)(4, 5) — «Пас»;
A: (3, 4)(4, 5)(5, 6) — «Пас»;
B: (3, 4)(4, 5) — «Пас»;
A: (4, 5)(5, 6) — «Пас»;
B: (4, 5) — «У меня на лбу число 5».

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

Действительно, если игрок B видит число N, а игрок A видит число N + 1, то цепочка у A состоит из N + 1 пар, а у B — из N пар, и на каждом раунде обе цепочки становятся короче на одну пару. Таким образом, после N − 1 раундов обе цепочки сократятся на N − 1 вариант, и в цепочке игрока B останется единственный вариант, что и позволит ему (правильно) назвать собственное число.

Отметим, что в любой работающей стратегии свое число первым сможет назвать только тот из игроков, который видит меньшее число. Это безусловно так для пары (1, 2), потому что игрок, видящий на другом число 1, может сделать вывод о своем числе сразу же, на первом раунде игры, в то время как у игрока, видящего число 2, на первом раунде есть выбор между вариантами (1, 2) и (3, 2).

Кроме того, ясно, что за один ход можно угадать только число 2, потому что на первом раунде игры ни про какую иную пару чисел нет никакой дополнительной информации, позволяющей выбрать между двумя вариантами. Поэтому, если (предположим!) для какой-то пары соседних чисел (N, N + 1) первым назвать число cможет тот, кто видит большее из них, то это означает, что он каким-то образом исключил вариант (N + 2, N + 1). Но исключить его он смог бы только в том случае, если у его партнера существует возможность угадать свое число N + 1 в этой паре раньше, то есть если для большей пары чисел существует работающая стратегия с меньшим числом ходов. Продолжая рассуждать таким образом, мы придем к выводу, что для какой-то пары, отличной от (1, 2), существует возможность угадать число на первом раунде, а это, как было указано выше, невозможно.

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

А теперь — маленькая вишенка на «тортик» игры о двух числах. Любая оптимальная стратегия эквивалентна описанной выше стратегии «укорачивающейся цепочки», так как приводит к угадыванию числа тем же самым игроком и за то же самое количество ходов. А раз так, то оптимальные стратегии могут быть найдены разумными игроками без всякой предварительной договоренности друг с другом!

Вернемся к нашей игре с тремя игроками, причем сначала разрешим им договориться об общей стратегии. Почти все, что мы выше написали про игру с двумя соседними числами, может быть распространено и на эту игру, но с немного более сложным устройством цепочек. Поэтому начнем именно с описания построения цепочек.

Дальше все ситуации в игре мы будем описывать тройками (a, b, c), в которых одно из чисел равно сумме двух других, считая, что первое число записанно на лбу у игрока А, второе — у игрока B, а третье — у игрока C. Назовем корневой тройкой чисел такую, в которой два из трех чисел равны (а третье равно их сумме).

Введем на множестве наших троек (a, b, c) функцию F, отображающую каждую корневую тройку в себя, а каждую некорневую — в меньшую тройку, следующим образом:

F(a, b, a + b) = (a, b, |a − b|), если a ≠ b, и F(a, a, 2a) = (a, a, 2a).

Использование этой функции позволяет по произвольной тройке построить цепочку уменьшающихся троек, которая рано или поздно приведет к корневой тройке. Далее мы будем выписывать эти цепочки в обратном порядке, то есть начинать с корневой тройки. Например, если игрок C видит на игроках A и B числа a = 16 и b = 44, то он строит следующую цепочку:
C: (8, 4, 4) (8, 12, 4) (16, 12, 4) (16, 12, 28) (16, 44, 28) (16, 44, 60).

Жирным в тройках выделены наибольшие числа. Они при переходе к предыдущей тройке заменяются на разность двух остальных чисел.

Пусть у самого игрока C написано число 60. Тогда игрок A будет видеть 44 и 60, а игрок B будет видеть 16 и 60, поэтому их цепочки будут такими:
A: (8,4,4) (8,12,4) (16,12,4) (16,12,28) (16,44,28) (16,44,60) (104,44,60),
B: (8,4,4) (8,12,4) (16,12,4) (16,12,28) (16,44,28) (16,44,60) (16,76,60).

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

В приведенном выше примере игра по стратегии будет происходить следующим образом (звездочкой помечены ходы активных игроков, после которых все игроки вычеркивают первый вариант из своих цепочек):
A*: (8, 4, 4) (8, 12, 4) (16, 12, 4) (16, 12, 28) (16, 44, 28) (16, 44, 60) (104, 44, 60) — «Пас»;
B*: (8, 12, 4) (16, 12, 4) (16, 12, 28) (16, 44, 28) (16, 44, 60) (16, 76, 60) — «Пас»;
C: (16, 12, 4) (16, 12, 28) (16, 44, 28) (16, 44, 60) — «Пас»;
A*: (16, 12, 4) (16, 12, 28) (16, 44, 28) (16, 44, 60) (104, 44, 60) — «Пас»;
B: (16, 12, 28) (16, 44, 28) (16, 44, 60) (16, 76, 60) — «Пас»;
C*: (16, 12, 28) (16, 44, 28) (16, 44, 60) — «Пас»;
A: (16, 44, 28) (16, 44, 60) (104, 44, 60) — «Пас»;
B: (16, 44, 28) (16, 44, 60) (16, 76, 60) — «Пас»;
C*: (16, 44, 60) — «У меня число 60».

Докажем, что такая стратегия работает, и более того, что в ней число будет названо игроком, имеющим самую короткую цепочку. Это вполне очевидно: начала цепочек у всех игроков совпадают, отличаются они только последними тройками. Следовательно, за каждый раунд каждая цепочка сократится как минимум на одну тройку (часто — больше, если в течение одного раунда несколько игроков побывают в роли активного). Поэтому неизбежно наступит момент, когда самая короткая из трех цепочек сократится до одного варианта. В этот момент, согласно стратегии, игрок и сможет назвать число.

Так как более короткой является цепочка у того игрока, на лбу которого написана сумма двух остальных чисел, то свое число сможет назвать (пользуясь нашей стратегией) именно этот игрок. А поскольку именно он в этот момент является активным, то остальные два игрока в этом раунде не смогут вычеркнуть этот вариант, пока не подождут его хода. Но так как он в этот момент не пасует, а называет число, то именно он всегда будет первым.

Оказывается, как и в игре с двумя числами, и при любой иной работающей стратегии первым сможет назвать число только тот игрок, у которого оно равно сумме остальных.

Это утверждение легко проверить для корневых троек (аналогично тому, как это мы делали в игре с двумя числами для пары (1, 2)). Предположим, что это не так для некоторого номера хода n и некоторой некорневой тройки (a, b, c). Если в этой тройке игрок C может назвать свое число, и это число c не равно a + b, то c = |a − b|. Но это означает, что игрок C каким-то образом сделал вывод о том, что его число не равно a + b. Это эквивалентно тому, что в тройке (a, b, a + b) кто-то из двух остальных игроков смог бы назвать свое число, причем сделать это раньше! Мы, таким образом, пришли к другой некорневой тройке, в которой число может быть названо на ходе с меньшим номером. Продолжая таким образом, мы получим некорневую тройку, в которой можно назвать число на первом же ходу, что невозможно.

Так же несложно (ну, почти так же) можно убедиться и в оптимальности стратегии. Из существования оптимальной стратегии (снова-таки, аналогично игре с двумя числами) можно вывести ее единственность, а это, в свою очередь, означает, игрокам не нужна договоренность о стратегии!