37
МАТЕМАТ ИЧ Е С К ИЙ
КР У ЖОК
не можем ничего сделать с этим числом, мы даже затрудняемся прочесть его вслух. Кажется, вопрос нашего телезрителя опять остается без ответа! Постойте, я сказал «нашего телезрителя»? Маэстро, признавайтесь, это опять ваши происки? Вы опять, скрываясь под псевдонимом, прислали воп-
рос, чтобы нарушить спокойное течение нашей передачи? – Нет-нет, я не имею никакого отношения к случившемуся сегодня. Хотя, вы знаете… Недавно я рассказал Бусеньке о том, как легко и приятно вводить вас в ступор с помощью безобидного на вид вопроса…
Принесите еще шляп!
и обозначют цвета также числами от 0 до n – 1. Каждый мудрец видит все шляпы, кроме своей. Значит, он знает сумму всех чисел, кроме одного (своего). Тогда пусть k-й мудрец называет свой цвет, исходя из предположения, что сумма всех чисел дает при делении на n остаток k. Например, пусть n = 8 и третий мудрец увидел, что сумма чисел у остальных мудрецов равна 20. Тогда он должен назвать число 7, потому что только в случае, когда у него шляпа 7-го цвета, сумма всех чисел (она в этом случае равна 27) дает остаток 3 при делении на 8. Заметим, что описанная стратегия весьма «экономна» в том смысле, что для каждого расклада шляп лишь один мудрец угадывает цвет шляпы. Номер этого мудреца совпадает с остатком суммы всех цветов при делении на n. Взглянем на эту экономность с другой точки зрения. Пусть судья заранее составит список из всех возможных способов выдать мудрецам шляпы разных цветов. Каждый такой способ будем называть раскладом шляп. Работа немаленькая, ведь количество всех раскладов равно (потому что каждому из n мудрецов можно дать шляпу любого из n цветов). После этого пусть судья подслушает, о чем договорились мудрецы на совещании, и возле каждого расклада шляп в своем списке запишет, какие мудрецы угадывают цвет шляпы для этого расклада. Лемма 1. Для каждого k пометка «угадывает k-й мудрец» будет стоять в точности возле раскладов. Иными словами, каждый мудрец выигрывает в точности на от общего числа раскладов. Доказательство. Допустим, что судья перебирает все варианты расклада шляп следующим образом: сначала он фиксирует цвета всех шляп, кроме шляпы k-го мудреца, а после этого размышляет, какую из n шляп выдать k-му мудрецу. Так как цвета всех
К.КОХАСЬ
РАССМОТРИМ СЛЕДУЮЩУЮ ИЗВЕСТ- ную задачу о мудрецах. Происходит следующий конкурс. По кругу стоят n мудрецов. Судья надевает каждому мудрецу шляпу одного из n цветов. Каждый мудрец видит шляпы, надетые на других мудрецов, но не видит своей собственной. По сигналу мудрецы (одновременно) должны высказать гипотезу о цвете своей шляпы. Если хотя бы один мудрец угадал цвет своей шляпы, считается, что мудрецы выиграли конкурс. Перед проведением конкурса мудрецы имели возможность посовещаться, а во время конкурса никакая передача информации не разрешена. Могли ли они на этом совещании придумать стратегию, позволяющую им выиграть в любом случае? Под стратегией понимается набор инструкций (свой для каждого мудреца), которыми должны руководствоваться мудрецы при выдвижении своих гипотез. Каждая такая инструкция – это набор правил вида «если вижу на таких-то мудрецах такие-то цвета шляп, то выдвигаю такую-то гипотезу». В частности, стратегия должна быть детерминированной, т. е. не содержать действий, совершаемых с некоторой вероятностью. Это значит, что при повторении конкурса с тем же самым набором шляп мудрецы дадут те же самые ответы. Решение этой задачи весьма красиво. Мудрецы нумеруют себя числами от 0 до n – 1
DOI: https://doi.org/10.4213/kvant20191106