Let $ n,k$ be given positive integers satisfying $ k\le 2n - 1$. On a table tennis tournament $ 2n$ players take part, they play a total of $ k$ rounds match, each round is divided into $ n$ groups, each group two players match. The two players in different rounds can match on many occasions. Find the greatest positive integer $ m = f(n,k)$ such that no matter how the tournament processes, we always find $ m$ players each of pair of which didn't match each other.
Problem
Source: Chinese TST 2009 1st quiz P2
Tags: ceiling function, pigeonhole principle, induction, graph theory, combinatorics proposed, combinatorics
21.03.2009 11:38
Clearly, (if I have understood the problem correctly), $ f(n, 2n-1) = 0, f(n, 2n-2) = 2$. For smaller $ k$, each player misses at least $ 2n - k - 1$ players, we have to ensure the presence of a $ K_m$. Does it have a Ramsey theoretic flavour?
15.04.2009 18:42
Claim: $ f(n,k) = \begin{cases}\lceil \frac {2n}{k + 1}\rceil, & k\text{ is odd} \\ \lceil \frac {2n}{k}\rceil, & k\text{ is even}\end{cases}$. Lemma: To create a set of $ q$ players where each player has played each other player in the set, a minimum of $ q - 1$ rounds are required when $ q$ is even and a minimum of $ q$ rounds are required when $ q$ is odd, and this minimum is achievable. Proof: Clearly we need to have $ \frac {q(q - 1)}{2}$ matches total. Each round can have $ \frac {q}{2}$ matches if $ q$ is even and $ \frac {q - 1}{2}$ if $ q$ is odd. The lower bound follows. To show that the minimum is achievable, we will first work with $ q$ odd. Draw a regular $ q$-gon, then draw a line through a vertex and through the opposite side. Then, in the first round, the matches whose corresponding lines are perpendicular to this drawn line will play. Doing this one round for each vertex yields a construction for the lower bound. Now consider $ q = 2p$. Let $ g(p)$ be the required number of rounds for $ p$ players. Use the first $ g(p)$ rounds to complete $ p$-cliques for each of two halves, then use the next $ p$ rounds to connect each of the players in the first half to the players in the second half (connect $ a_i$ to $ b_{i + j}$ in round $ j$ where indices are taken mod $ p$). If $ p$ is odd, we can eliminate one of these rounds by connecting $ a_i$ to $ b_i$ in each of the first $ g(p)$ rounds. Thus, the lemma follows. Now, it is clear by the lemma that if $ k$ is odd, we can make $ \lceil \frac {2n}{k + 1}\rceil$ cliques of size at most $ k + 1$ and have some extra edges. The most we might possibly be able to choose here is $ \lceil \frac {2n}{k + 1}\rceil$ since we can only choose one from each clique, so $ f(n,k) \leq \lceil\frac {2n}{k + 1}\rceil$. Similarly for $ k$ even, $ f(n,k) \leq \lceil\frac {2n}{k}\rceil$. Now consider the graph $ G$ where the vertices are the players and there is an edge between the vertices if two players were matched. We see immediately that the maximal degree of this graph is at most $ k$. Thus, it can be $ k + 1$-colored, which immediately shows that $ f(n,k) \geq \lceil\frac {2n}{k + 1}\rceil$ since at least one of the colors contains at least $ \lceil\frac {2n}{k + 1}\rceil$ vertices by the pigeonhole principle. Since this is a vertex-coloring, the vertices of this color must form an independent set, so $ f(n,k) \geq \lceil\frac {2n}{k + 1}\rceil$ for all $ n, k$. This settles the case for $ k$ odd. For $ k$ even, we will consider each connected component $ C$. We will split into three cases: 1: C is an odd cycle If C is an odd cycle, then the chromatic number of $ C$ is $ 3$. We also know that we cannot make an odd cycle in the case $ k = 2$, so $ k \geq 3$. Thus, $ \chi(C) \leq k$. 2: C is a complete graph We know from the lemma that we are unable to make a $ k + 1$-clique using $ k$ rounds, so if $ C = K_m$, then $ m \leq k$. Thus, $ \chi(C) = m \leq k$. 3: C is neither an odd cycle or a complete graph Then Brooks' Theorem gives that $ \chi(C) \leq k$, since the maximal degree of $ C$ is at most $ k$. Thus, we have shown that $ \chi(C) \leq k$ for any connected component $ C$ of $ G$. Since the chromatic number of $ G$ is simply the maximum of the chromatic numbers of the connected components, we know that $ \chi(G) \leq k$ as well. It follows that $ G$ can be $ k$-colored and thus $ f(n,k) \geq \lceil\frac {2n}{k}\rceil$ for even $ k$. We thus arrive at our result: $ f(n,k) = \begin{cases}\lceil \frac {2n}{k + 1}\rceil, & k\text{ is odd} \\ \lceil \frac {2n}{k}\rceil, & k\text{ is even}\end{cases}$
17.01.2014 07:00
This problem pretty much follows from the base cases and induction. The answers are $ f(n,k) =\begin{cases}\lceil\frac{2n}{k+1}\rceil, & k\text{ is odd}\\ \lceil\frac{2n}{k}\rceil, & k\text{ is even}\end{cases} $. I'll use Lemma 1 of the above solution in my solution. We'll induct on $n$ (it's not really an induction). Ok, our base case is basically in Lemma 1. To be more explicit for the $k$ even case, if we have $k+1$ vertices, we know that (by Lemma 1) we can't have all vertices having degree $k$. So say $v_1$ has degree $< k$. Then by choosing $v_1$, we can't choose $d(v_1)+1 \le k < k+1$ of the vertices anymore. So we can still pick some vertex, so we get 2 vertices chosen. For the $k$ odd case, say we choose some vertex $v_1$ to be in our independence set. Then we remove $d(v_1)+1 \le k+1$ vertices from also being in the set. Similarly, each vertex chosen knocks out $k+1$ from being other possible vertices, so we can choose at least ${\lceil}\frac{2n}{k+1}{\rceil}$ vertices to be in our set. Construction is just a bunch of ${K}_{k+1}$'s and another complete graph with the remainder. For the $k$ even case, we need to be a little more sharp in our estimates. If the graph is disconnected, we're done by induction on the components. (Use that $\lceil{x}\rceil+\lceil{y}\rceil \ge \lceil{x+y}\rceil$) So we're going to choose vertices to appear in our independence set again. Say $v_1$ is in our set. Then we can't pick any vertices in $N(v_1)$ or $v_1$. $v_1$ eliminates $k+1$ vertices from consideration. Ok, now choose a vertex $v_2$ that is in $N(N(v_1))$ but not eliminated from consideration yet (this is possible by connectivity). Then $v_2$ eliminates AT MOST $k$ vertices from consideration (it's neighbors, and itself, but it shares a neighbor with $v_1$, who is already eliminated). Continuing this process (looking at $N(N(v_2))$ etc.), assume that $m < {\lceil}\frac{2n}{k}{\rceil}$. We get that $k+1+k \cdot (m-1) \le k+1+k \cdot {\lceil}\frac{2n}{k}{\rceil} -k \le k+1+2n-2-k < 2n$. ($k \cdot (m-1) < 2n-2-k$ because both $k$ and $2n$ are even, so our remainder can be at most $k-2$). So we can still add another vertex. So this gives us our set. Construction for the $k$ even case is the same as the odd case.
21.03.2015 13:35
The case for $k$ odd can be tackled by applying Turan's theorem on the number of pairs which were not matched.If we give an edge to a pair who were not matched,itis to be seen that the least number of edges in the $2n$ graph is $n(2n-1-k)$.(at least) Now if we apply Turan's theorem on these number of edges then,we get that $K_{r+1}$ may be guaranteed where $r-1<\frac{2n}{k+1}\le r$ and the construction of the Turan graph will give a plausible tournament if $k$ is odd.But if $k$ is even then the Turan graph cannot satisfy the tournament.Then we have the colour the vertices(this time a vertex given to a matched player) and show the chromatic number to be at most $k$.