Условие

Путешественник приехал на остров, каждый из 100 жителей которого или лжец, который всегда обманывает, или рыцарь, который всегда говорит правду. При этом среди жителей острова есть хотя бы один лжец.

Лжецы решили лгать таким образом, чтобы каких бы 50 жителей путешественник не собирал вместе, присутствующие среди них лжецы всегда отвечали на вопрос о числе рыцарей среди собранных туземцев так, чтобы путешественник получал один и тот же набор из 50 ответов.

Какое наибольшее число рыцарей могло быть на острове?

Ответ

Решая эту головоломку, нужно рассуждать следующим образом: рыцарей на острове менее 50, иначе путешественник, выбрав всех рыцарей, получил бы 50 ответов «пятьдесят», а, выбрав одного лжеца и 49 рыцарей, услышал бы иной набор ответов.

Получается, что лжецов на острове не менее 50 человек.

Поскольку набор ответов должен выглядеть правдоподобно, в наборе ответов должен быть 1 ответ «один», 2 ответа «два», 3 ответа «три», ..., 9 ответов «девять» и еще 5 неправдоподобных ответов. Из этого можно сделать вывод, что на острове может быть не больше 9 рыцарей.