https://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Shortlist_Problems/C5&feed=atom&action=history 2006 IMO Shortlist Problems/C5 - Revision history 2022-01-25T03:20:24Z Revision history for this page on the wiki MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Shortlist_Problems/C5&diff=24406&oldid=prev Boy Soprano II: problem and solution 2008-03-30T15:09:24Z <p>problem and solution</p> <p><b>New page</b></p><div>== Problem ==<br /> <br /> (''Argentina'') An &lt;math&gt;(n,k)&lt;/math&gt;-tournament is a contest with &lt;math&gt;n&lt;/math&gt; players held in &lt;math&gt;k&lt;/math&gt; rounds such that:<br /> :(i) Each player plays in each round, and every two players meet at most once.<br /> :(ii) If player &lt;math&gt;A&lt;/math&gt; meets player &lt;math&gt;B&lt;/math&gt; in round &lt;math&gt;i&lt;/math&gt;, player &lt;math&gt;C&lt;/math&gt; meets player &lt;math&gt;D&lt;/math&gt; on round &lt;math&gt;i&lt;/math&gt;, and player &lt;math&gt;A&lt;/math&gt; meets player &lt;math&gt;C&lt;/math&gt; in round &lt;math&gt;j&lt;/math&gt;, then player &lt;math&gt;B&lt;/math&gt; meets player &lt;math&gt;D&lt;/math&gt; in round &lt;math&gt;j&lt;/math&gt;.<br /> Determine all pairs &lt;math&gt;(n,k)&lt;/math&gt; for which there exists an &lt;math&gt;(n,k)&lt;/math&gt;-tournament.<br /> <br /> ''This problem also appeared on the 2007 [[TST]] for Korea.''<br /> <br /> == Solution ==<br /> <br /> Let &lt;math&gt;t&lt;/math&gt; be the greatest integer such that &lt;math&gt;2^t&lt;/math&gt; divides &lt;math&gt;n&lt;/math&gt;. Then there exists an &lt;math&gt;(n,k)&lt;/math&gt;-tournament if and only if &lt;math&gt;k \le 2^t - 1&lt;/math&gt;.<br /> <br /> We first prove that if &lt;math&gt;k \le 2^t - 1&lt;/math&gt;, then there exists an &lt;math&gt;(n,k)&lt;/math&gt;-tournament. Since we may partition our &lt;math&gt;n&lt;/math&gt; players into &lt;math&gt;n/2^t&lt;/math&gt; different groups of size &lt;math&gt;2^t&lt;/math&gt;, it suffices to prove this for &lt;math&gt;n=2^t&lt;/math&gt;.<br /> <br /> To this end, let us label the &lt;math&gt;2^t&lt;/math&gt; players with the elements of &lt;math&gt;(\mathbb{Z}/2\mathbb{Z})^t&lt;/math&gt;, and label the different rounds with distinct nonzero elements of &lt;math&gt;(\mathbb{Z}/2\mathbb{Z})^t&lt;/math&gt;. In the round with label &lt;math&gt;j&lt;/math&gt;, let player &lt;math&gt;a&lt;/math&gt; meet player &lt;math&gt;a+j&lt;/math&gt;. We then have a &lt;math&gt;(2^t,k)&lt;/math&gt; tournament, for if &lt;math&gt;a-b = c-d = i&lt;/math&gt;, then &lt;math&gt;a-c = b-d&lt;/math&gt;, for all &lt;math&gt;a,b,c,d \in (\mathbb{Z}/2\mathbb{Z})^t&lt;/math&gt;.<br /> <br /> We next prove that if &lt;math&gt;k &gt; 2^t-1&lt;/math&gt;, then there is no &lt;math&gt;(n,k)&lt;/math&gt;-tournament. For this, we first prove an intermediate result.<br /> <br /> '''Lemma.''' The number of players in any minimal subtournament of an &lt;math&gt;(n,k)&lt;/math&gt;-tournament is a power of 2.<br /> <br /> ''Proof.'' We induct on &lt;math&gt;k&lt;/math&gt;. The case &lt;math&gt;k=0&lt;/math&gt; is trivial.<br /> <br /> Suppose now that all minimal subtournaments of any &lt;math&gt;(n,k-1)&lt;/math&gt;-tournament have sizes that are powers of 2. Then in any &lt;math&gt;(n,k)&lt;/math&gt;-tournament, the minimal subtournaments, ignoring the last round, are of powers of 2. Let &lt;math&gt;S&lt;/math&gt; be the set of players for such a minimal tournament, and for any player &lt;math&gt;a&lt;/math&gt; in the &lt;math&gt;(n,k)&lt;/math&gt;-tournament, let &lt;math&gt;K(a)&lt;/math&gt; be the player &lt;math&gt;a&lt;/math&gt; meets in round &lt;math&gt;k&lt;/math&gt;. Then either &lt;math&gt;K(S) = S&lt;/math&gt;, or &lt;math&gt;K(S)&lt;/math&gt; and &lt;math&gt;S&lt;/math&gt; are disjoint; furthermore, &lt;math&gt;K&lt;/math&gt; induces an [[isomorphism]] of tournaments from &lt;math&gt;S&lt;/math&gt; to &lt;math&gt;K(S)&lt;/math&gt;, so &lt;math&gt;S&lt;/math&gt; and &lt;math&gt;K(S)&lt;/math&gt; have the same cardinality. It follows that the minimal subtournament of the &lt;math&gt;(n,k)&lt;/math&gt;-tournament containing any element of &lt;math&gt;S&lt;/math&gt; has size either &lt;math&gt;|S|&lt;/math&gt; or &lt;math&gt;2|S|&lt;/math&gt;, completing the inductve step and proving the lemma. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> Now, suppose that there exists an &lt;math&gt;(n,k)&lt;/math&gt;-tournament for &lt;math&gt;k &gt; 2^t-1&lt;/math&gt;. Then every minimal sub-tournament of our tournament has a multiple of &lt;math&gt;2^{t+1}&lt;/math&gt; players, since each must have a size that is a power of 2, and no two players meet more than once. It follows that &lt;math&gt;2^{t+1}&lt;/math&gt; divides &lt;math&gt;n&lt;/math&gt;, a contradiction. Therefore no &lt;math&gt;(n,k)&lt;/math&gt;-tournament exists for &lt;math&gt;k &gt; 2^t-1&lt;/math&gt;, as desired. &lt;math&gt;\blacksquare&lt;/math&gt;<br /> <br /> <br /> {{alternate solutions}}<br /> <br /> == Resources ==<br /> <br /> * [[2006 IMO Shortlist Problems]]<br /> * &lt;url&gt;viewtopic.php?p=875001#875001 Discussion on AoPS/MathLinks&lt;/url&gt;<br /> <br /> <br /> [[Category:Olympiad Combinatorics Problems]]</div> Boy Soprano II