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