Question

В парламенте Анчурии какие-то депутаты враждуют (причем у каждого есть хотя бы один враг), какие-то дружат, а некоторые безразличны друг другу. Дружба, вражда и безразличие взаимны, причем для каждого депутата работает принцип: «Друг моего врага является и моим врагом». Докажите, что у какого-то депутата врагов больше, чем друзей.

Answer 1

Возьмем любого депутата. По условию у него есть хотя бы один враг – выберем любого врага. Из этих двух враждующих депутатов именем А назовем того, у кого больше друзей, а другого депутата назовем Б (если у них поровну друзей, то без разницы, кто из них А, а кто Б). Если у депутата А врагов больше, чем друзей, то мы нашли такого депутата (из утверждения задачи). Если же у депутата А врагов не больше, чем друзей, то обозначим количество его друзей через X. Тогда у депутата Б друзей не больше X (из этих двух депутатов мы договорились называть именем А того, у кого друзей не меньше), но при этом его врагами точно являются все друзья депутата А (их ровно X), да еще и сам депутат А (итого уже X + 1), а может кто-то еще (можно игнорировать, потому что у Б уже насчитали больше X врагов).
Итак, здесь у депутата Б не больше X друзей, но больше X врагов, – тогда депутат Б подходит под утверждение задачи