Разбор отбора Яндекс Кружка по ИИ. Часть 2

Вступление

Постов давно не было... Извините... Приступим!

N. Рыцари и лжецы

Одна из моих любимых тем комбинаторики - логические задачи. Это одна из них

Условие:
На острове живут жители $P_1, P_2, \dots, P_{100}$. Каждый из них либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт.

Житель $P_i$ утверждает:

Среди остальных 99 жителей ровно $i-1$ рыцарей.

Определите все возможные значения общего числа рыцарей на острове.

Во первых, заметим, что каждый житель острова сказал разные фразы. Из этого следует, что, если рыцарь и есть, то он только 1.

Допустим, рыцарь есть.: Тогда он точно находится под номером 1, потому что он должен сказать "Среди остальных 99 жителей 0 рыцарей". Но рассмотрим после этого жителя номер 2. Он сказал "Среди остальных 99 жителей 1 рыцарь", это правда, хотя он обязан быть лжецом. Противоречие, такой конфигурации не может существовать.

Допустим, рыцарей нет: Рассмотрим того же первого жителя, его фраза, что среди 99 жителей 0 рыцарей является правдой, а по условию рыцарей быть не может. Тоже противоречие.

По условию задачи, если не существует возможного значения числа рыцарей, в ответе мы записываем $\varnothing$. Это и будет нашим ответом.

Заключение

Посты будут. Правда. Я не ленивый.