48-я Международная Математическая OлимпиадаВьетнам, Ханой, 2007 год

Среди участников математического соревнования некоторые дружат между собой; если $A$ дружит с $B$, то и $B$ дружит с $A$. Назовём группу участников кликой, если каждые двое из них дружат. (В частности, любая группа, состоящая менее чем из двух человек, является кликой.) Назовем количество человек в клике ее размером. Известно, что наибольший размер клики, состоящей из участников соревнования, является четным числом. Докажите, что всех участников можно рассадить в две комнаты так, чтобы наибольший из размеров клик, находящихся в одной комнате, был равен наибольшему из размеров клик, находящихся в другой комнате.

Комментарий/решение

Допустим это неверно. Но по условию это надо доказать, что значит, что это является верным утверждением. А значит это противоречие предположению. Поэтому это верно => доказано