ВсОШ 2022, муниципальный этап, 10 класс, задача 7
( баллов) На острове живёт рыцаря и лжецов; имена всех жителей различны. Знающий об этом приехавший турист попросил каждого из жителей написать на листке имён лжецов. Каждый рыцарь написал верно имён лжецов, а каждый лжец написал произвольный список из имён, в котором точно нет его собственного имени. Какое наибольшее количество лжецов турист сможет гарантированно определить по этим данным?
Ответ
Ответ: .
Решение. Для начала приведём стратегию для лжецов, позволяющую гарантированно вычислить не больше из них. Назовём рыцарей , , , , а лжецов — , , , . Все рыцари укажут в своих списках , , , . Пусть для каждого целого группа лжецов , , , укажет в своих списках , , , , а также всех лжецов, кроме самих , , , . А лжецов , , , укажут в своём списке , , , , , , , . Турист, увидев полученные списки, не сможет гарантированно вычислить ни одного лжеца среди , , , (это и означает, что он вычислит не более лжецов). Действительно, если бы вдруг турист заявил, что — лжец, то он мог бы ошибиться: группа из человек, в которую входил , вполне могла полностью состоять только из рыцарей, которые в своих списках одинаково указали на всех остальных людей, которые вполне могли оказаться лжецами.
Теперь поймём, почему турист всегда сможет вычислить хотя бы лжецов. Факт того, что человек указывает в списке имён предполагаемых лжецов равносилен тому, что он называет рыцарями оставшихся человек (включая себя). Все рыцаря заведомо называют рыцарями друг друга. Заметим, что если некоторый человек назовёт рыцарями группу из человек, не все из которых называют рыцарями эту же группу людей, то — точно лжец (если бы он был рыцарем, то все названные им люди тоже были бы рыцарями, а тогда бы они назвали рыцарями эту же группу). Групп из человек, называющих рыцарями друг друга, не больше (ведь ), и они не пересекаются. Следовательно, турист точно может гарантировать, что оставшиеся люди, не входящие в такие группы, являются лжецами. И таких людей хотя бы .