Question

В шеренгу стоят 40 человек, некоторые из которых рыцари (всегда говорят правду), а некоторые лжецы (всегда лгут). Они пронумерованы слева направо числами от 1 до 40. Каждый человек произнес ровно одну фразу. А именно, K-ый человек сказал: <<Справа от меня в шеренге не менее K лжецов.>> Сколько рыцарей может быть в этой шеренге?

Answer 1

До 20, так как если 21-ой человек-рыцарь, то он солгал. С первого по двадцатый максимум.

Answer 2

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

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

Теперь предположим, что K-ый человек является лжецом. Это означает, что он лжет, и в его утверждении находится ложь. Он говорит, что справа от него не менее K лжецов. Но если он лжец, то справа от него K-1 человек будут рыцарями (потому что лжецы всегда лгут).

Теперь рассмотрим случай, когда K-ый человек действительно лжец, и справа от него K-1 человек рыцари. Тогда он говорит, что справа от него не менее K лжецов, что является ложью, так как рыцари всегда говорят правду.

Итак, мы видим, что нам нужно найти такое K, при котором утверждение K-го человека истинно, то есть число лжецов справа от него действительно не менее K.

Мы начинаем с K = 1. Если K = 1, то первый человек говорит, что справа от него нет лжецов. Но это невозможно, так как все 40 человек либо рыцари, либо лжецы.

Если K = 2, то второй человек говорит, что справа от него не менее 2 лжецов. Это также невозможно, так как если справа от него два лжеца, то он сам должен быть рыцарем, но он лжет, что противоречит предположению.

Продолжая аналогично, когда K = 3, третий человек говорит, что справа от него не менее 3 лжецов. Так как каждый человек может быть либо рыцарем, либо лжецом, и каждый следующий человек в утверждении предыдущего человека должен быть лжецом, чтобы утверждение оставалось истинным, то возможным является только один вариант: первые 3 человека - рыцари, а остальные - лжецы.

Таким образом, в шеренге может быть 3 рыцаря.