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

Разберем задачу про рыцарей и лжецов. На острове живут рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. 100 жителей выстроились в ряд. Каждый видит всех, кто стоит перед ним, но не видит тех, кто стоит за ним. Первый молчит.

Второй и все стоящие на четных местах говорят: «Передо мной стоит не больше одного рыцаря».

Третий и все стоящие на нечетных местах говорят: «Передо мной стоит не больше двух лжецов».

а) Какое наименьшее число рыцарей могло стоять в этом ряду?

Рассмотрим, когда число рыцарей минимально. Чтобы на четных местах говорили правду, перед ними должно стоять не более одного рыцаря. Чтобы на нечетных местах говорили правду, перед ними должно стоять не более двух лжецов.

Предположим, что все стоящие на четных местах – лжецы, а все стоящие на нечетных местах, начиная с третьего, – рыцари. Тогда перед каждым лжецом на четном месте стоит хотя бы один рыцарь (иначе бы он говорил правду). Перед каждым рыцарем на нечетном месте стоит не более двух лжецов (иначе бы он лгал).

Рассмотрим такую ситуацию: Первый – рыцарь, второй – лжец, третий – рыцарь, четвертый – лжец, и так далее. В этом случае, все, кто стоит на четных местах, лгут, а все, кто стоит на нечетных местах (начиная с третьего), говорят правду.

Тогда получается, что рыцари стоят на нечетных местах, а лжецы - на четных. Количество нечетных мест в ряду из 100 человек – 50. Следовательно, минимальное количество рыцарей – 50.

Однако, первый человек молчит, значит, он может быть и рыцарем, и лжецом. Если первый лжец, то количество рыцарей уменьшится на 1, и станет 49. В этом случае, второй (стоящий на четном месте) говорит правду, так как перед ним стоит 1 рыцарь. Третий (стоящий на нечетном месте) говорит правду, так как перед ним стоит 1 лжец.

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

б) Какое наибольшее число рыцарей могло стоять в этом ряду?

Чтобы найти максимальное число рыцарей, предположим, что лжецов минимальное количество. Рассмотрим такую ситуацию, что все стоящие на четных местах - рыцари. В этом случае, они говорят правду, значит, перед каждым из них стоит не более одного рыцаря. Это возможно, если перед каждым рыцарем, стоящим на четном месте, стоит лжец.

Тогда получается, что все стоящие на нечетных местах - лжецы (кроме первого, который молчит). А все, кто стоит на четных местах - рыцари. Число четных мест в ряду из 100 человек – 50. Значит, количество рыцарей – 50.

Если первый - рыцарь, то перед вторым (стоящим на четном месте) будет стоять 1 рыцарь, и он будет говорить правду. Перед третьим (стоящим на нечетном месте) будет стоять 1 рыцарь, и он будет лгать, так как перед ним должен стоять не более 2 лжецов. Значит, третий должен быть лжецом.

В таком случае, максимальное количество рыцарей – 99.

Ответ: а) 1, б) 99