Олимпиадная задача по математике про рыцарей и лжецов

Question

Олимпиадная задача по математике про рыцарей и лжецов

Человек Человек паратаратц Ученик (105), закрыт 1 год назад

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

Answer 1

Заметим, что если второй - рыцарь, то первый обязан быть рыцарем. Но тогда, рассуждения людей, стоящих на четных местах неверны, ведь перед ними минимум 2 рыцаря и значит, они все лжецы. Если 2 - лжец, то неважно, кто первый, его утверждение истинно, что невозможно. Тогда Мы выяснили, что 1 и 2 - рыцари, а все четные - лжецы. Рассмотрим 3. Перед ним стоят 2 рыцаря => он обязан быть рыцарем. Аналогично с 5, перед ним 1 лжец (это 4) => 5 - рыцарь. А далее, все, стоящие на нечетных местах после 5 - лжецы. Мы получили, что расстановка рыцарей и лжецов однозначна, поэтому ответ на оба пункта одинаков и равен 4

Answer 2

Давайте рассмотрим эту задачу шаг за шагом.

**а) Наименьшее число рыцарей:**

1. Первый молчит, поэтому мы не можем определить его статус.
2. Второй говорит, что перед ним не больше одного рыцаря. Это может быть правдой (если первый - рыцарь) или ложью (если первый - лжец).
3. Третий говорит, что перед ним не больше двух лжецов. Это может быть правдой (если первые двое - рыцари) или ложью (если один из первых двоих - лжец).

Поскольку мы ищем наименьшее число рыцарей, допустим, что второй и третий - лжецы. Тогда первый также должен быть лжецом.

Продолжая этот процесс, мы можем предположить, что все, кто стоит на четных местах, - лжецы, и все, кто стоит на нечетных местах, - также лжецы, до тех пор, пока это не противоречит их утверждениям.

**б) Наибольшее число рыцарей:**

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

Продолжая этот процесс, мы можем предположить, что все, кто стоит на четных местах, - рыцари, и все, кто стоит на нечетных местах, - рыцари, до тех пор, пока это не противоречит их утверждениям.

Теперь давайте вычислим оба этих значения.

Наибольшее число рыцарей, которое могло стоять в этом ряду, составляет 51.

Теперь давайте найдем наименьшее число рыцарей.

Наименьшее число рыцарей, которое могло стоять в этом ряду, составляет 2 (так как всего 98 лжецов).

Итак:
а) Наименьшее число рыцарей: 2
б) Наибольшее число рыцарей: 51