В королевстве живут рыцари. Любые два из них либо враждуют (и такие среди них есть!), либо дружат, либо друг к другу безразличны. Друг врага рыцаря —враг этого рыцаря. Докажите, что хотя бы у одного рыцаря врагов больше, чем друзей.

Давайте докажем утверждение от противного. Предположим, что у каждого рыцаря не меньше друзей, чем врагов.

Возьмем любого рыцаря и назовем его А. Посмотрим на его связи с другими рыцарями. У него есть минимум один друг (по предположению), но поскольку мы предположили, что у каждого рыцаря не меньше друзей, чем врагов, то у рыцаря А есть по крайней мере один враг. Обозначим его как B.

Теперь рассмотрим связи этого врага B. По предположению, у него должно быть не меньше друзей, чем врагов. Значит, он тоже имеет по крайней мере одного друга. Обозначим этого друга как C.

Продолжая этот процесс, мы можем найти последовательность рыцарей A, B, C, …, Z, где каждый следующий рыцарь имеет по крайней мере одного друга из предыдущего рыцаря. Но среди этих рыцарей обязательно есть повторения, потому что их всего конечное число, а связей у них сколь угодно много.

Пусть некоторый рыцарь, обозначим его как X, является не впервые повторяющимся рыцарем в нашей последовательности. Значит, X имеет по крайней мере двух врагов из предыдущих рыцарей этой последовательности. Но это означает, что у X врагов больше, чем друзей, что противоречит нашему предположению.

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