|
2007-07-25, 12:49
|
#1 |
Dec 2005
3048 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 
|
|
|
|
2007-07-25, 14:03
|
#2 | |
"Bob Silverman"
Nov 2003
North of Boston
1D8416 Posts |
Quote:
|
|
|
|
|
|
2007-07-25, 14:08
|
#3 |
|
Dec 2005
22×72 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... 
|
|
|
|
|
2007-07-25, 22:09
|
#4 |
Jun 2003
The Texas Hill Country
32×112 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 2007-07-25 at 22:14 |
|
|
|
|
2007-07-25, 23:34
|
#5 |
Aug 2002
Ann Arbor, MI
1B116 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. |
|
|
|
|
2007-07-26, 07:09
|
#6 |
|
Dec 2005
3048 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 | 2016-11-15 03:31 |
| Saturday 3/04 2007 Lunar Eclipse | mfgoode | Lounge | 59 | 2010-10-19 15:36 |
| Microsoft Office 2007 questions | ixfd64 | Lounge | 3 | 2009-12-20 03:39 |
| k*2^n-1 primes in 2007 | Kosmaj | Riesel Prime Search | 1 | 2008-01-01 03:43 |
| Crypto 2007 | R.D. Silverman | Lounge | 2 | 2007-08-08 20:24 |
