Question

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

Answer 1

Для начала заметим, что если депутата какого-то типа спросить о депутате того же типа, то он ответит "рыцарь" и они станут разного типа (и про них мы точно будем знать, что среди них ровно 1 рыцарь и 1 лжец).

Ежели теперь депутаты будут иметь разный тип, то ответ будет "лжец" и депутаты стануть одного типа (но неизвестно какого). Зато если теперь спросить в обратную сторону (снасала спросили первого относительно второго, теперь второго относительно первого). Тогда это соответствует предыдущему случаю. Тогда мы знаем, что теперь среди них ровно 1 рыцарь и 1 лжец.

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

Ответ: да, можно

Answer 2

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

Для определения типа каждого депутата, нам нужно задать вопрос следующего вида каждому депутату: "Если бы я спросил тебя, ты – рыцарь?". Предположим, депутат, которого мы спрашиваем, является рыцарем. Тогда, поскольку рыцарь всегда говорит правду, он ответит "Да", потому что если бы он был опрошен, он бы сказал правду о своем типе (рыцаре). Однако, так как рыцарь отвечает правдиво, его ответ будет ложным, и мы знаем, что он на самом деле лжец. Если же депутат является лжецом, он также ответит "Да", потому что если бы он был опрошен, он бы солгал о своем типе (лжеце). Таким образом, его ответ будет верным, и мы знаем, что он действительно рыцарь.

Таким образом, задавая этот вопрос каждому депутату и анализируя ответы, мы можем определить их тип (рыцарь или лжец). Итоговое количество рыцарей будет равно количеству тех депутатов, которые ответили "Да", а количество лжецов будет равно количеству тех, кто сменил свой тип после ответа на вопрос.