Олимпиадная задача по математике По кругу стоят 175человек, каждый из которых либо рыцарь, либо лжец (лжецы всегда лгут, а рыцари всегда говорят правду). Каждый из стоявших сказал: «Через одного человека от меня есть лжец». Найдите минимальное возможное число лжецов среди этих $$175$$ человек.

Предыдущий
вопрос Следующий
вопрос

Предположим, что рыцарей в кругу больше, чем лжецов. Пусть у нас есть $$r$$ рыцарей и $$l$$ лжецов ($$r + l = 175$$).

Так как каждый человек сказал, что через одного от него находится лжец, это означает, что все лжецы должны стоять рядом с рыцарями. Таким образом, среди $$r$$ рыцарей должно быть $$l$$ лжецов, и среди $$l$$ лжецов должен быть еще один лжец, который находится рядом с рыцарем.

Это означает, что $$l \geq r$$ (если бы было $$l < r$$, то в последнем круге лжецов не хватило бы, чтобы замкнуть цепочку).

Подставляем $$r = 175 - l$$ в неравенство и получаем $$l \geq 175 - l$$, откуда следует, что $$l \geq 87.5$$. Так как количество лжецов должно быть целым числом, то наименьшее возможное число лжецов будет $$l = 88$$.

Итак, минимальное возможное число лжецов среди 175 человек равно 88.