Решение задачи 159

Условие:

В ряд стоят 100 человек (каждый человек либо рыцарь, либо лжец). Первый сказал: «Количество рыцарей среди нас -- делитель числа 1», второй сказал: «Количество рыцарей среди нас -- делитель числа 2» и так далее. Сколько в ряду рыцарей?

Решение:

Заметим сразу, что в ряду может быть 0 рыцарей. Действительно, 0 не является делителем никакого числа, поэтому каждый из ста лжецов соврет. Теперь предположим, что в ряду k рыцарей, 1⩽k⩽100. Тогда люди с номерами k, 2k, 3k, .., [100/k]k скажут правду, а остальные солгут ([x] = целая часть числа x). Действительно, на k делятся только числа вида nk (n∈ℤ). Получается, что количество рыцарей в ряду будет [100/k]. Но мы вначале предположили, что в ряду k рыцарей, значит осталось решить уравнение [100/k] = k. Заметим, что при k, больших 10, левая часть меньше 10, а при k, меньших 10, левая часть больше 10, значит единственным корнем может быть только k=10. Подстановкой убеждаемся, что число 10 действительно корень.

Ответ: 0 или 10.