|
|
 |
Условие
Кащей заточил в темницу толпу пленников и сказал им: «Завтра вам предстоит испытание. Я выберу нескольких из вас (кого захочу, но минимум троих), посажу за круглый стол в каком-то порядке (в каком пожелаю) и каждому на лоб наклею бумажку с нарисованной на ней фигуркой. Фигурки могут повторяться, но никакие две разные фигурки не будут наклеены на одинаковое число людей. Каждый посмотрит на фигурки остальных, а своей не увидит. Подавать друг другу какие-то знаки запрещено. После этого я наклейки сниму и велю всех развести по отдельным камерам. Там каждый должен будет на листе бумаги нарисовать фигурку. Если хоть один нарисует такую, какая была у него на лбу, всех отпущу. Иначе останетесь здесь навечно».Как пленникам договориться действовать, чтобы спастись?
Решение
Поскольку разных фигурок разное количество, какая-то фигурка использована больше остальных. Назовём её главной. Если фигурок любой другой формы хотя бы на две меньше, то каждый пленник видит, какая фигурка главная. Если все нарисуют её, среди них будут и угадавшие верно.Пусть это не так и, например, главная фигурка — квадрат, следующая по числу — круг, причём кругов ровно на один меньше, чем квадратов. Тогда пленники с квадратами на лбу будут видеть одинаковое количество кругов и квадратов и не смогут определить наверняка главную фигурку (остальные, как и раньше, будут видеть, какая фигурка главная, и могут нарисовать её). Для этого случая есть несколько спасительных алгоритмов.
Первый — из двух кандидатов в главные фигурки назвать ближайшую по часовой стрелке. Докажем, что хоть кто-то угадает. Будем учитывать только квадраты и круги, игнорируя остальных пленников. Может ли после каждого квадрата по часовой стрелке следовать круг? Нет, так как квадратов больше. Тот пленник с квадратом, после которого по часовой стрелке следует квадрат, угадает и всех спасёт.
Работает и противоположный алгоритм: из двух кандидатов в главные фигурки называть не ту, которая ближе всего по часовой стрелке. Для доказательства тоже рассмотрим лишь круги и квадраты. Как минимум в одном месте после пленника с квадратом следует по часовой стрелке пленник с кругом. Этот пленник с квадратом верно нарисует свою фигурку.
