Difference between revisions of "2007 IMO Problems/Problem 3"
m (restore extlink) |
(solution) |
||
| Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
| − | + | We use capital letters to denote sets of competitors. We write <math>cl.C</math> to denote that <math>C</math> is a clique. | |
| + | Some properties of cliques are listed below: | ||
| + | <math>(1)\,D\subset E \vee cl.E \Rightarrow cl.D</math> | ||
| + | <!-- to be continued --> | ||
| + | |||
==External links== | ==External links== | ||
Revision as of 20:35, 29 October 2007
Problem
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 competitors 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 in 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.
Solution
We use capital letters to denote sets of competitors. We write 
to denote that 
is a clique.
Some properties of cliques are listed below:
External links
| 2007 IMO (Problems) • Resources | ||
| Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
| All IMO Problems and Solutions | ||
