IMO Shortlist 2015 problem C7


Kvaliteta:
  Avg: 0,0
Težina:
  Avg: 9,0

In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least 3, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most 2015 unsociable groups, prove that it is possible to partition the company into 11 parts so that no two enemies are in the same part.

(Russia)

Izvor: https://www.imo-official.org/problems/IMO2015SL.pdf