olymmath

IMO 2007 Problem 3

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Author: Vasily Astakhov, Russia

Dataset text AI-MO AoPS. Quoted with source.

Official text: IMO 2007 official English paper, page 1.

Also ISL 2007 C6.

Solutions

Official solution Solution 1 by the IMO Problem Selection Committee

The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

Similar problems

These problems have the most words in common with this statement.

Locator imo/2007/p3 · Tag 2AQV9RDS51 · Edit this page on GitHub · Keys: j next, k previous