mersenneforum.org Problem 3 from IMO 2007
 Register FAQ Search Today's Posts Mark Forums Read

 2007-07-25, 12:49 #1 Kees     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
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D8416 Posts

Quote:
 Originally Posted by Kees 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
.....induction.

 2007-07-25, 14:08 #3 Kees     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 Wacky     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 Kevin     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 Kees     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

 Similar Threads Thread Thread Starter Forum Replies Last Post didgogns Msieve 1 2016-11-15 03:31 mfgoode Lounge 59 2010-10-19 15:36 ixfd64 Lounge 3 2009-12-20 03:39 Kosmaj Riesel Prime Search 1 2008-01-01 03:43 R.D. Silverman Lounge 2 2007-08-08 20:24

All times are UTC. The time now is 00:13.

Sun Jun 4 00:13:16 UTC 2023 up 289 days, 21:41, 0 users, load averages: 0.94, 1.03, 0.94