Задача 077 — Задачи на Графы

В кружке $n$ ребят, причём любые двое ребят либо дружат, либо враждуют. Оказалось, что у каждого из ребят ровно 10 врагов в этом же кружке, причём если $A$ дружит с $B$ , но враждует с $C$ , то $B$ и $C$ враждуют. Найдите все возможные значения $n$ .

Подсказка

Если все враги одного из двух друзей являются врагами другого, то у любых двух друзей одни и те же враги. При этом друг моего друга — мой друг, иначе у меня был бы враг, который не враждует с моим другом.

Решение

Ответ. 11, 12, 15, 20.

Решение. Если все враги одного из двух друзей являются врагами другого, то у любых двух друзей одни и те же враги. При этом друг моего друга — мой друг, иначе у меня был бы враг, который не враждует с моим другом. Поэтому все кружковцы разбиваются на группы, где каждый дружит с каждым, причём в каждой группе на 10 человек меньше, чем во всём кружке. Пусть в каждой группе $k$ человек. Тогда 10 должно делиться на $k$ , а всего ребят в кружке — $10+k$ . С другой стороны, если $m$ — делитель числа 10 , то кружок, состоящий из $m+1$ группы размера $k=10 / m$ , где любые двое из одной группы дружат, а из разных групп — враждуют, удовлетворяет условию задачи Перебирая теперь делители числа 10, получаем ответ.