|
|
 |
Условие
Путешественник прибыл на остров, где живут 50 аборигенов, каждый из которых либо рыцарь, либо лжец. Все аборигены встали в круг, и каждый назвал сначала возраст своего соседа слева, а потом возраст соседа справа. Известно, что каждый рыцарь назвал оба числа верно, а каждый лжец какой-то из возрастов (по своему выбору) увеличил на 1, а другой – уменьшил на 1. Всегда ли путешественник по высказываниям аборигенов сможет определить, кто из них рыцарь, а кто лжец?Решение 1
Выберем любого аборигена – будем называть его Петей, – и покажем, как найти его возраст. Мысленно наденем на каждого второго аборигена шапку, начиная с Пети. Занумеруем аборигенов без шапок, идущих за Петей по часовой стрелке: 1, 2, ..., 24, 25.
Заметим, что каждый абориген верно сообщает сумму возрастов своих соседей (если сложить названные аборигеном числа). Сложим числа, названные 1-м, 3-м, ..., 25-м аборигенами без шапок – это будет сумма возрастов всех аборигенов в шапках плюс возраст Пети. Сложим числа, названные 2-м, 4-м, ..., 24-м аборигенами без шапок – это будет сумма возрастов всех аборигенов в шапках минус возраст Пети. Вычтя из первой суммы вторую и поделив на 2, получим возраст Пети.
Зная возраст любого аборигена, легко узнать, кто его соседи, по их ответам.
Решение 2
Для удобства будем считать, что в круге стоят через одного 25 мужчин и 25 женщин. Покажем, как различить мужчин (женщины определяются аналогично). Заметим, что два высказывания о возрасте одной женщины отличаются на 1 тогда и только тогда, когда ее соседи – рыцарь и лжец. Поэтому достаточно опознать одного мужчину: далее по кругу определяются все остальные.
Разберём два случая.
1) Для одной из женщин высказывания об её возрасте различаются на 2. Тогда оба её соседа – лжецы, и, как сказано выше, все мужчины определяются.
2) Таких женщин нет. Все мужчины разбиваются на группы: внутри такой группы оба соседа каждой женщины говорят об её возрасте одно и то же. Но пока не известно, какие группы состоят из лжецов, а какие – из рыцарей.
Сложив все числа, названные мужчинами, получим удвоенную сумму возрастов женщин. Теперь сложим первые числа, названные мужчинами. Если полученная сумма имеет ту же чётность, что сумма возрастов женщин, то среди мужчин чётное число лжецов, а если не совпадает – нечётное. Поскольку из двух возможных вариантов количество лжецов чётно только в одном, путешественник определит, какой из вариантов правильный.
