В парламенте есть депутаты двух типов – рыцари и лжецы, всего их ровно 120. Спикер может...

Question

В парламенте есть депутаты двух типов – рыцари и лжецы, всего их ровно 120. Спикер может любого депутата спросить про любого другого «Он рыцарь?» или «Он лжец?». Если депутат отвечает «Да», его тип тут же меняется на противоположный (лжец становится рыцарем, а рыцарь лжецом). Может ли спикер опросить депутатов так, чтобы на конец опроса все депутаты были одного типа?

Answer 1

Разделим депутатов на пары. В каждой паре спрашиваем у обоих депутатов: "Твой напарник - рыцарь?".
- Получили два нет: один рыцарь, второй лжец (если один рыцарь, то второй - лжец, так как рыцарь сказал правду. Если один лжец, то второй рыцарь, так как лжец солгал).
- Получили "да-нет". Если первый изначально был бы рыцарем, то он стал бы лжецом, а второй - лжец, но лжец не ответил бы нет. Значит, первый был лжецом, стал рыцарем, а второй был и остался лжецом.
- Получили "нет-да". Если первый был бы рыцарем, то второй сначала был лжецом, но лжец не ответил бы да. Значит, первый - лжец, второй был рыцарем, а стал лжецом.
- Получили два да. Если первый был бы до ответа рыцарем, то и второй был до ответа рыцарем. Но после ответа первый поменял тип, и второй, будучи рыцарем, не мог назвать его рыцарем. Значит, первый был лжецом, стал рыцарем, стал лжецом, а второй был лжецом, стал рыцарем.

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