Fifty teams participate in a round robin competition over 50 days. Moreover, all the teams (at least two) that show up in any day must play against each other. Prove that on every pair of consecutive days, there is a team that has to play on those two days.
Problem
Source: Singapore IMO TST 2008, Problem 6
Tags: induction, combinatorics proposed, combinatorics
13.09.2008 23:38
Really wonderful problem! I hope I have a solution, I will just state the main idea here. We have to prove that if $ K_n$ is decomposed into $ n$ complete graphs then no 2 of them are disjoint. We can prove a stronger statement: "If $ K_n$ is decomposed into less than $ n+k-1$ complete graphs, then no $ k$ of them are pairwise disjoint (this holds for $ k\geq2$). Furthermore, there is no decomposition into less than $ n$ graphs, besides the trivial one." This statement can be proved by induction on $ n$, pretty straightforward.
25.05.2009 07:51
Sorry for my poor combinatorics, shasha said using induction could prove the stronger statement , but I'm still puzzled.Could anyone say it more clearly? Many thanks.
12.06.2013 04:19
This is nothing but a particular case of the de Bruijn-Erdös incidence theorem, stating that given a set of $n$ elements $A = \{a_1,a_2,\ldots,a_n\}$, and $m>1$ subsets of it, such that each pair of elements in $A$ is contained in one and only one subset, then $m\geq n$, with equality only in the cases when (up to a reindexing) the subsets are $\{a_1,a_n\}, \{a_2,a_n\}, \ldots, \{ a_{n-1}, a_n\}$ and $\{a_1,a_2,\ldots,a_{n-1}\}$, or when $n=k^2+k+1$ for some integer $k$, each subset contains $k+1$ elements, each element is contained in $k+1$ subsets, and any two subsets intersect (in precisely one element, of course). See http://www.renyi.hu/~p_erdos/1948-01.pdf. The elements are the teams, and the subsets are the days, made of the players that showed up that day. Clearly this is also saying things about finite projective planes. For the last case, which is of most interest, it is known a model exists when $k$ is a power of a prime, and no other possibility is yet known to occur. Unfortunately, the problem setters either had no knowledge of this, or botched it! First, they only talk about consecutive days; in fact this is true for any two days. Second, $50$ is not of the form $k^2+k+1$ (so the issue of $k$ being a power of a prime is moot); therefore the only possibility is the first one mentioned - in one day all teams but one showed up, and in any other day, that last team showed up, with just, each day, another of the first teams. Therefore complete knowledge is acquired on the possible round-robin. It was not so difficult for $50$ to have been replaced by $57 = 7^2 + 7 + 1$, eh?
31.03.2018 09:28
related https://artofproblemsolving.com/community/c6h359803