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

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

Пусть — множество всех людей, которые назвали числа от 0 до а — множество всех людей, которые назвали числа от до Пусть — степень вершины Тогда по условию если — рыцарь, и в противном случае. Пусть в множестве ровно лжецов, а в множестве — ровно

Оценим количество ребер между людьми из разных множеств и

С одной стороны, не больше суммы степеней вершин множества откуда

С другой стороны, из каждой вершины множества не более ребер идет в вершины множества и значит, не менее ребер идет в вершины множества Отсюда

Получаем неравенство:

откуда Это означает, что всего лжецов не менее

Пример. Как и прежде, номер человека будет означать его ответ. Возьмем два множества людей:

и

Пусть в множестве никакие двое людей не дружат друг с другом, а в множестве — любые двое дружат. Далее, пусть человек и дружат тогда и только тогда, когда Тогда у человека всего друг:

У человека будет всего друзей:

из множества и все люди множества кроме него самого. При этом все люди в — лжецы, а в — рыцари. Видим, что все условия задачи выполняются.