mersenneforum.org Problem 3 from IMO 2007
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-07-25, 12:49 #1 Kees     Dec 2005 22·72 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

1D5816 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 110001002 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 433 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 22·72 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:07.

Fri Mar 31 00:07:14 UTC 2023 up 224 days, 21:35, 1 user, load averages: 1.22, 0.99, 0.88

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔