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

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

а) Рассмотрим возможные варианты. Пусть в ряду стоит рыцарь. Тогда второй скажет правду, что перед ним стоит не больше одного рыцаря. Но это не выполнится, так как перед ним стоит рыцарь. Следовательно, в ряду не может быть рыцарей.

Пусть в ряду стоят только лжецы. Тогда третий скажет правду, что перед ним стоят не больше двух лжецов. Так как перед ним стоит лжец, это условие выполняется. Проверим это для всех остальных лжецов. Обратим внимание, что третий лжец говорит правду, иначе это противоречие. Таким образом, наименьшее число рыцарей в ряду равно 0.

б) Предположим, что в ряду стоит только лжецы. Тогда первый лжец скажет первое лживое утверждение, что перед ним стоит не больше одного рыцаря. Это означает, что перед ним стоит рыцарь. Противоречие. Значит, в ряду есть хотя бы один рыцарь.

Так как перед первым лжецом обязательно должен стоять рыцарь, то перед вторым лжецом обязательно должен стоять лжец. Значит, перед первым и вторым лжецами стоят рыцари. Продолжаем таким образом и приходим к выводу, что перед каждым лжецом стоят рыцари, а перед каждым рыцарем стоит лжец. Это соответствует условию задачи.

Таким образом, наибольшее число рыцарей в ряду равно 50.