20070725, 12:49  #1 
Dec 2005
304_{8} Posts 
Problem 3 from IMO 2007
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. A small postscriptum: I don't have a solution yet 
20070725, 14:03  #2  
"Bob Silverman"
Nov 2003
North of Boston
1D84_{16} Posts 
Quote:


20070725, 14:08  #3 
Dec 2005
2^{2}×7^{2} Posts 
like in one of my algebra textbooks straight after a theorem:
the proof is long and tedious, is done by induction and is therefore left as an exercise... 
20070725, 22:09  #4 
Jun 2003
The Texas Hill Country
3^{2}×11^{2} Posts 
OK, I'm confused.
Assume that A, B and C are competitors, and that A is a friend of B, and also that B is a friend of C. Therefore we have the cliques {}, {A}, {B}, {C}, {A,B}, {B,C}. Is it true that we additionally have the cliques {A,C} and {A,B,C} iff A and C are also friends? Or are we to interpret "mutual" in some way to unconditionally infer the transitive relationship? Last fiddled with by Wacky on 20070725 at 22:14 
20070725, 23:34  #5 
Aug 2002
Ann Arbor, MI
1B1_{16} Posts 
"Is it true that we additionally have the cliques {A,C} and {A,B,C} iff A and C are also friends?"
Yes. "Or are we to interpret "mutual" in some way to unconditionally infer the transitive relationship?" No, mutual (aka, symmetric) does not imply transitive. 
20070726, 07:09  #6 
Dec 2005
304_{8} Posts 
Mutual does (as I interpret the question) indeed not imply transitivity.
Note that the question becomes trivial if friendship is transitive 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What is the problem here?  didgogns  Msieve  1  20161115 03:31 
Saturday 3/04 2007 Lunar Eclipse  mfgoode  Lounge  59  20101019 15:36 
Microsoft Office 2007 questions  ixfd64  Lounge  3  20091220 03:39 
k*2^n1 primes in 2007  Kosmaj  Riesel Prime Search  1  20080101 03:43 
Crypto 2007  R.D. Silverman  Lounge  2  20070808 20:24 