Задача 2. Гномы из десяти кланов

Что означает каждое высказывание

Назвав клан, гном утверждает: «из этого клана пришли одни лжецы». Это правда, если в названном клане нет ни одного рыцаря, и неправда, если в нём есть хотя бы один рыцарь.

• Рыцарь говорит правду — значит, он назвал клан, в котором нет рыцарей.

• Лжец лжёт — значит, он назвал клан, в котором есть хотя бы один рыцарь.

Нам нужно доказать, что лжецов много, поэтому ищем места, где лжецы обязательно есть. Прочитаем вывод в обратную сторону: клан, в котором есть рыцарь, мог назвать только лжец. Рыцарь назвать его не мог — он сказал бы неправду.

Кланы с рыцарями назвали только лжецы

Пусть рыцари есть ровно в $m$ кланах ($m$ — какое-то число от $0$ до $10$). По условию каждый из этих кланов назвали ровно $10$ гномов, и по шагу 1 все они лжецы.

Не посчитали ли мы кого-то дважды? Нет: каждый гном назвал только один клан, поэтому гномы, назвавшие разные кланы, — разные. Значит, эти $m$ кланов назвали вместе $10 \cdot m$ разных гномов, и все они лжецы:

Рыцарей не больше $10m$

Теперь посчитаем рыцарей. Где они сидят? Каждый рыцарь входит в свой клан, а в этом клане, раз там есть он, есть рыцарь. Значит, все рыцари — в тех самых $m$ кланах с рыцарями. В каждом клане $10$ гномов, поэтому мест там всего $10m$ и

Соединим два вывода: рыцарей $\le 10m \le$ лжецов. Значит, лжецов не меньше, чем рыцарей, что и требовалось доказать.

Рассуждение годится при любом $m$: например, при $m = 0$ рыцарей нет совсем, и неравенство $0 \le 0$ тоже верно. Рисунок ниже показывает оба счёта на одном составе, где $m = 7$.

Поровну бывает

Доказательство закончено, но полезно убедиться, что оценка точная: рыцарей и лжецов может быть поровну.

Пусть кланы $1$–$5$ — одни рыцари, а кланы $6$–$10$ — одни лжецы. Каждый рыцарь называет один из кланов $6$–$10$, по $10$ рыцарей на клан, — это правда: там одни лжецы. Каждый лжец называет один из кланов $1$–$5$, по $10$ лжецов на клан, — это неправда: там рыцари. Каждый клан назван ровно $10$ раз, свой клан никто не называет. Рыцарей и лжецов по $50$.

А вот рыцарей больше, чем лжецов, не бывает — это и есть доказанное утверждение. В модели можно попробовать: при $51$ рыцаре и больше названия не раздаются.