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

Бір қатарда 100 адам тұр. Олардың әрқайсысы не өтірікші (олар әрқашан өтірік айтады), не сері (олар әрқашан шындықты айтады). Әр адам былай дейді: «Менің сол жағымда тұрған өтірікшілер саны, менің оң жағымда тұрған серілер санынан көп». Қатарда қанша өтірікші бар?

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

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

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