Примерно через пол года после поступления в магистратуру и переезда в Москву, то есть где-то в 2015 году, я периодически начал посещать мероприятия вроде «дня карьеры» в стенах МГУ. По существу это своеобразные выставки вакансий, где работодатели, заинтересованные в специалистах математического профиля демонстрируют, что они могут предложить, зазывают талантливую молодежь на стажировки, а самых перспективных и вовсе приглашают работать на постоянной основе. Можно как угодно относиться к этой практике — кому-то это кажется очень неуместным и неправильным занятием, расшатывающим образовательный процесс, а кому-то совсем наоборот. На мой взгляд, подобные мероприятия в любом случае несут в себе пользу, поскольку позволяют узнать побольше о рынке труда, порешать интересных задач «в стиле» заданий с собеседований и затариться бесплатными блокнотиками, чтобы было куда конспектировать потом матан.
Как раз на одном из таких мероприятий мне в первый раз довелось столкнуться с задачками про мудрецов и колпаки во всяких вариациях. Допускаю, что подобные задачи встречались мне и раньше, но к тому моменту совершенно вылетели из головы, поэтому было в новинку. Вот вольный пересказ одной из подобных задач:
Король рассердился на сотню своих мудрецов-советников и приказал устроить им испытание на рассвете: мудрецов выстроят в очередь (первый в очереди не видит перед собой никого, второй видит только первого, а последний видит всех), им завяжут глаза и наденут на головы колпаки. Колпак может быть либо черного, либо белого цвета, количество колпаков каждого цвета не ограничено и надеваются они случайным образом. После этого им снимут повязки с глаз и у каждого мудреца в очереди, начиная с последнего, громко спросят какого цвета на нем колпак. Он должен выкрикнуть только одно слово: «черный» или «белый». Если он назовет цвет своего колпака верно, то будет освобожден, а иначе ему отрубят голову на месте. Мудрецы совещались всю ночь и придумали способ сделать так, чтобы гарантированно выжило не менее 99 человек, а может и все 100 если повезет. Какую стратегию они придумали?
Прежде чем обсуждать эту очень «бородатую» задачу (если вы о ней еще не слышали, значит мне крупно повезло), хочу сказать, что мудрецов лично я всегда представлял совсем не в смешных колпаках, а примерно так:
Ну хорошо, задача ясна, осталось дело за малым. Первая стратегия, которая вообще всем приходит на ум, заключается в том, что каждый мудрец должен назвать цвет шляпы впереди стоящего. Это естественная и простая стратегия, но только если использовать её, то гарантированно выживут не более половины мудрецов (что маловато и грустно). Мудрецам необходимо так скоординироваться, чтобы каждый новый называемый цвет давал информацию впереди стоящим людям, причем как можно большую. Уверен, что после некоторого размышления (к чему призываю) вам придет на ум мысль, что наверное это задача на принципы четности и нечетности.
Действительно, давайте представим себе такую вот стратегию:
Будем считать что черная шляпа обозначается числом 1, а белая числом 0 (так мы сможем размышлять о сумме цветов шляп). Мудрец в конце очереди (который видит всех) называет вслух четность суммы всех шляп, которые он видит перед собой (если сумма четная говорит «черный», а если нечетная то «белый»). Ему может повезти и этот цвет совпадет с цветом его шляпы, а может и не повезти, к сожалению (но тогда он погибнет за благую цель и спасет всех остальных). Следующий мудрец услышит ответ предыдущего, а также увидит все шляпы перед собой. Ему необходимо посчитать четность суммы всех цветов шляп, которые он видит перед собой, а затем сравнить эту четность с тем, что он услышал от предыдущего мудреца. Если эти четности совпадают, то на нем, очевидно, белая шляпа, а иначе черная, и он легко назовет свой цвет. Следующим в очереди будет чуть сложнее — ему необходимо вспомнить ответ первого мудреца, вспомнить ответы всех, кто уже успел назвать свой цвет после первого (назовем четность суммы этих ответов числом x), а также посчитать четность суммы шляп, которые он видит перед собой (а эту четность назовем y). Теперь ему нужно будет сравнить ответ первого мудреца с четностью числа x+y. Если ответ первого мудреца совпадает с четностью x+y, то на том, кто сейчас отвечает белая шляпа, а иначе черная.
Осталось только заметить, что все наши размышления про сравнение четности легко описываются разностью по модулю два (это и есть остатки от деления на два), и процесс схематически выглядит так (первый отвечающий на схеме слева):
Но если все это так хорошо описывается арифметическими операциями по какому-то модулю, то несложно обобщить решение для случая любого фиксированного числа цветов шляп и произвольного количества мудрецов. Для большей наглядности вот листинг алгоритма для решения этой задачи в случае n мудрецов и m цветов шляп:
Важно, что в этой задаче мудрецы выстроены в ряд и что-то по очереди произносят ответ вслух — это серьезные ограничения, которые и позволяют нам найти такое хорошее решение. Если представить себе, что всех мудрецов усадили в кружок, и, не показывая свой цвет, надели на голову шляпу одного из двух цветов, то мудрецы должны обладать какой-либо дополнительной информацией что-бы назвать правильный ответ. Так получается классическая задача о которой можно круто подискутировать. Тем не менее, даже здесь можно придумать интересные ограничения, при которых задача становится очень содержательной и занятной. Об одной из таких вариаций мне недавно любезно рассказала моя коллега Анастасия Быстрыгова, очень сильный математик и программист. Вот, что она мне написала:
Участвовали мы с командой в 2018м году в IPSC, соревновании по программированию, где встречаются как задачи в стиле ICPC (алгоритмические задачки с заранее определенными жюри ответами), так и оптимизационные (где жюри заранее не знает самый подходящий ответ, и участники борются в том, чтобы найти ответ лучше), игровые и какие-то шуточные.
Среди задач условием меня сразу зацепила задача про шапки, поскольку очень напомнила то, чем я занималась в научной сфере все годы бакалавриата, магистратуры и в 2018м продолжила заниматься в аспирантуре - расшифровкой функций, то есть восстановлением функции по частичкам сведений о ней при помощи определенных запросов.
Само условие той задачи вот https://ipsc.ksp.sk/2018/real/problems/h.html, но приведем тут его основное содержание.
a) 13 игроков договариваются до начала игры, в каком случае каждый поднимает руку,
b) затем начинается игра, все закрывают глаза, каждому игроку надевают на голову шапку одного из двух цветов (пусть будут красный и синий),
с) затем все открывают глаза и видят номера цветов всех шапок кроме своей, по заранее обговоренной стратегии каждый поднимает руку в зависимости от того, что увидел,
d) после того, как каждый игрок (не)поднял руку, все называют цвета надетых на них шапок,
Цель - придумать такую стратегию до игры, чтобы независимо от того, какого цвета шапки наденут на игроков, каждый по тому, как другие игроки подняли руки, поймет, шапка какого цвета на него надета.
Решение задачи надо было написать на неизвестном нам языке программирования Lua 5.3, но сложность в сдаче была естественно не в этом :-) Сложность - придумать саму стратегию.
Частичный балл можно было заработать, решив эту задачу для случая, когда цветов всего 2, а полный - если цветов 4000.
Очень интересная формулировка, и случай двух цветов опять похож на задачу про четность и нечетность. Действительно, давайте представим себе такую стратегию решения для этого случая:
На этапе поднятия рук: каждый мудрец считает четность суммы цветов (по тому же принципу, черная шапка это 1, белая это 0) остальных мудрецов, и поднимает руку только если сумма нечетна.
На этапе ответа на вопрос о цвете своей шляпы: Мудрец под номер i выбирает любого другого под номером j, считает четность суммы всех цветов шляп на мудрецах с номером, отличным от j (потому что он их видит), а после сравнивает эту четность с четностью ответа мудреца j (поднятая рука значит четность 1, опущенная — 0). Если четности совпали, на мудреце i белая шляпа, иначе — черная.
Принцип принятия решения в этой задаче совершенно отличается от стратегии в первой задаче, но логика вычислений в чем-то сходна. Все дело в том, что каждый мудрец видит перед собой равное количество человек, и у них есть дополнительный этап обмена информации в виде «поднятия руки». Описанная выше стратегия схематически выглядит примерно так:
Вот листинг кода, который демонстрирует этот подход, в случае когда цветов всего два. Если до сих пор не до конца ясно, как работает стратегия, код должен немного помочь:
Частичный балл мы уже заработали, отлично. Но что делать со случаем, когда цветов не два, а 4000? Здесь не пройдет идея четности, а вычитать по произвольному модулю мы просто так не можем, потому что поднятая рука это всего лишь один бит информации. Но постойте-ка, откуда тогда число 4000? Здесь у опытного человека перещелкивает и он наверняка догадывается, что речь идет о битовых представлениях числа. Да и к тому же 4000 на что-то намекает, поскольку 2^12 = 4096. Значит и число мудрецов (13) не спроста выбрано. Принцип решения я умудрился нащупать сам, и это было очень интересно порешать самостоятельно! Вам рекомендую попробовать тоже, но далее здесь процитирую объяснение Насти, поскольку оно наполнено красочными замечаниями:
Для случая 4000 цветов все должно быть хитрее, и приятно, что мы, совместно рассуждая, довели его до верного решения. Частично меня на мысль натолкнула теорема из моей научки о сложности расшифровки функций вида f(x_1, x_2, ..., x_n) = x_i xor x_j. Для любопытных это Proposition 6 https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.5123&rep=rep1&type=pdf, идея которой - не поиск самих значений i, j, а восстановление этих номеров по битам в их бинарном представлении.
Сразу заметим, что в нашей задаче игроков 13, цветов 4000, 4000 < 2^12, то есть возможно надо рассматривать не цвета, а их двоичное представление, 12 игроков как раз будут что-то делать, чтобы восстановить все 12 битов цвета шапки, а 13й игрок чем-то еще пригодится.
Надеюсь, вы успели немного осознать эту информацию, потому что сразу приведем решение задачи:
1) Опишем стратегию для игрока с номером i (i = 1, 2, ..,11, 12): игрок i смотрит, чему равен бит с номером (i-1) в двоичном представлении цветов номера шапки всех остальных игроков, и поднимает руку, если сумма этих битов нечетна.
2) Игрок 13 поднимает руку, если сумма всех битов в двоичном представлении цветов шапок всех остальных 12 игроков нечетна.
Восстановление цветов при описанной стратегии следующее.
1) Игрок с номером j (j != i), видит всех игроков, которых видит игрок с номером i, за исключением самого j. Он также может посчитать четность числа битов с номером (i-1) в двоичном представлении цветов шапок всех этих игроков. Если четность, подсчитанная игроком j, равна четности, подсчитанной игроком i, то (i-1)й бит в бинарном представлении цвета шапки игрока j равен 0, иначе - 1.
Таким образом, после этого шага игрок 13 восстановил все биты в цвете своей шапки, игрок 1 восстановил все биты кроме 0го, игрок 2 все биты кроме 1го и т.д.
2) По действиям 13го игрока каждый игрок восстановит недостающий бит. Рассмотрим на примере игрока 1. Игрок 1 видит шапки всех игроков, которых видит игрок 13, кроме своей. Он также как и 13й игрок считает четность всех битов цветов шапок игроков 2-12, также он знает четность всех найденных битов цвета своей шапки. А 13й игрок знает эту же информацию + недостающий бит цвета шапки 1го игрока. Значит, по (не)совпадению четностей, подсчитанных игроком 1 и игроком 13, игрок 1 поймет, чему равен 0й бит цвета его шапки.
Для любопытных решение жюри вот https://ipsc.ksp.sk/2018/real/solutions/h.html, в авторском решении приводится еще одна стратегия для случая 2 цветов.
Хорошо изобразить схему этой идеи на картинке у меня пока не получилось (но может быть я дополню материал позднее). Получается что мы просто возвращаемся к идее четности, воспользовавшись тем фактом, что битность для представления цвета не превышает 12, а один человек может держать контрольную сумму для восстановления символа у того, кто не видит достаточно информации о конкретном своем бите в представлении числа. Очень красиво и элегантно. Хоть схемы и нет, зато я набросал код, который может прояснить идею:
Вот такие получаются хитрецы-мудрецы. Стоит отметить, что все вышеперечисленные размышления это довольно специфические вариации на тему помехоустойчивых кодов, о которых можно (и нужно) читать очень много интересного и полезного, чего всем советую.
Спасибо большое Насте Быстрыговой за отличные идеи для материала, а вам за внимание!
Желаю вам не терять голову, иначе на чем же носить разноцветные шляпы?