Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, I тур регионального этапа

По кругу сидят 100 человек. Некоторые из них --- рыцари, всегда говорящие правду, остальные --- лжецы, которые всегда лгут. Для некоторого натурального числа $k < 100$ каждый из сидящих произнёс фразу: «Следующие $k$ людей, сидящих за мной по часовой стрелке --- лжецы». Чему могло быть равно число $k$? ( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Любому из делителей числа 100, кроме 1, уменьшенному на 1: 1, 3, 4, 9, 19, 24, 49, 99.
Решение. Если бы все сидящие были лжецами, все они сказали бы правду. Значит, среди них есть рыцарь. После него сидят $k$ лжецов. У того из них, который сидит рядом с рыцарем, следующие $k-1$ человек --- лжецы, и так как он лжёт, то $k$-ый по счёту после него --- рыцарь. Рассуждая таким образом дальше, убеждаемся, что между двумя последовательными рыцарями за столом сидят $k$ лжецов. Таким образом, все сидящие за столом разбиваются на группы по $k+1$ человеку, и потому 100 должно делиться на $k+1$. Обратно, если 100 делится на $k+1$, рассадка людей за столом группами из рыцаря и $k$ сидящих за ним лжецов удовлетворяет условиям задачи.