Question

В комнате находятся 100 человек, каждый из которых либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт, причём все они разного роста. Каждый из находящихся в комнате сказал ровно одну из двух фраз: <<Хотя бы 10 лжецов ниже меня>>; <<Хотя бы 10 лжецов выше меня>>. Какое наименьшее число рыцарей может быть в комнате?

Answer 1

При наибольшем количестве лжецов будет наименьшее количество рыцарей.
Покажем, что лжецов не более 20.
Действительно, предположим, что лжецов хотя бы 21 и посмотрим, что сказал 11 по росту из лжецов.
Если он сказал "Хотя бы 10 лжецов выше меня", то он сказал правду (он 11 по росту, а значит ровно 10 лжецов выше, чем он), но правду он сказать не мог.
Если он сказал "Хотя бы 10 лжецов ниже меня", то он также бы сказал правду, так как по крайней мере 21-11=10 лжецов ниже, чем он.
Отсюда лжецов не более 20.

Покажем, что 20 лжецов может быть.

В случае, если 10 самых высоких - лжецы и 10 самых низких также лжецы, и при этом 10 самых высоких сказали "Хотя бы 10 лжецов выше меня", а 10 самых низких - " Хотя бы 10 лжецов ниже меня", то все соответствует условиям.
Очевидно, что 10 самых высоких лжецов солгали (вообще нет 10 человек из данных 100, которые были бы выше их, а тем более лжецов). Аналогично с самыми низкими лжецами.
80 рыцарей, которые являются оставшимися людьми, могут сказать что угодно. Всегда ровно 10 лжецов, которые выше, чем они и ровно 10 лжецов, которые ниже.

Ответ: 80 рыцарей.

Answer 2

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

Рассмотрим утверждение одного из лжецов, который говорит "Хотя бы 10 лжецов ниже меня". Пусть этот лжец имеет рост K. Тогда он утверждает, что среди 99 человек, стоящих ниже него, есть как минимум 10 лжецов. Но если бы это было правдой, то среди 100 человек было бы как минимум 11 лжецов, что невозможно. Значит, это утверждение лживо, и в комнате есть менее 10 лжецов, стоящих ниже человека с ростом K.

Аналогично рассмотрим утверждение лжеца, который говорит "Хотя бы 10 лжецов выше меня". Это утверждение также ложно, потому что если бы это было правдой, то среди 100 человек было бы как минимум 11 лжецов, что невозможно.

Итак, мы знаем, что среди 100 - N лжецов нет ни 10 лжецов, стоящих ниже, ни 10 лжецов, стоящих выше рыцарей. Значит, среди первых N человек должно быть как минимум 10 рыцарей. При этом все оставшиеся 100 - N человек будут лжецами.

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