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