8-я олимпиада им. Шалтая Смагулова, 7 класс, 3 тур

В ряд встали 100 человек. Каждый из них либо лжец (который всегда лжёт), либо рыцарь (который всегда говорит правду). Каждый говорит: «Слева от меня больше лжецов, чем рыцарей справа от меня». Сколько в ряду лжецов?

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

Допустим, что число лжецов больше 50. Тогда число рыцарей не больше 49.

Рассмотрим самого правого лжеца в ряду. Слева от него находятся все лжецы, кроме него самого, то есть не менее >50−1=49 лжецов. Таким образом, слева от него — не менее 49 лжецов. Справа от него уже нет других лжецов (он — самый правый лжец), следовательно, справа от него находятся только рыцари. Поскольку общее число рыцарей не больше 49, справа от него рыцарей не больше 49. Таким образом, слева от этого лжеца лжецов не меньше, чем справа от него рыцарей. То есть выполняется неравенство, о котором он говорит. Значит, его высказывание истинно. Но он лжец, а значит не может говорить правду — противоречие. Следовательно, наше предположение было неверно. Значит, лжецов не больше 50. Аналогично можно доказать, что их не меньше 50. Итак, в ряду 50 лжецов и 50 рыцарей.