Путешественник прибыл на остров, где живут 50 аборигенов, каждый из которых либо рыцарь, либо лжец. Все аборигены встали в круг, и каждый назвал сначала возраст своего соседа слева, а потом возраст соседа справа. Известно, что каждый рыцарь назвал оба числа верно, а каждый лжец какой-то из возрастов (по своему выбору) увеличил на 1, а другой — уменьшил на 1. Всегда ли путешественник по высказываниям аборигенов сможет определить, кто из них рыцарь, а кто лжец?
(Александр Грибалко)
I способ. Выберем любого аборигена — будем называть его Петей, — и покажем, как найти его возраст. Мысленно наденем на каждого второго аборигена шапку, начиная с Пети. Занумеруем аборигенов без шапок, идущих за Петей по часовой
Заметим, что каждый абориген верно сообщает сумму возрастов своих соседей (если сложить названные аборигеном числа). Сложим числа, названные
Зная возраст любого аборигена, легко узнать, кто его соседи, по их ответам.
Ответ: всегда.
II способ. Для удобства будем считать, что в круге стоят через одного
Разберём два случая.
1) Для одной из женщин высказывания об её возрасте различаются на 2. Тогда оба её соседа — лжецы, и, как сказано выше, все мужчины определяются.
2) Таких женщин нет. Все мужчины разбиваются на группы: внутри такой группы оба соседа каждой женщины говорят об её возрасте одно и то же. Но пока не известно, какие группы состоят из лжецов, а какие — из рыцарей.
Сложив все числа, названные мужчинами, получим удвоенную сумму возрастов женщин. Теперь сложим первые числа, названные мужчинами. Если полученная сумма имеет ту же чётность, что сумма возрастов женщин, то среди мужчин чётное число лжецов, а если не совпадает — нечётное. Поскольку из двух возможных вариантов количество лжецов чётно только в одном, путешественник определит, какой из вариантов правильный.