Given positive integer $ m \geq 17$, $ 2m$ contestants participate in a circular competition. In each round, we devide the $ 2m$ contestants into $ m$ groups, and the two contestants in one group play against each other. The groups are re-divided in the next round. The contestants compete for $ 2m-1$ rounds so that each contestant has played a game with all the $ 2m-1$ players. Find the least possible positive integer $ n$, so that there exists a valid competition and after $ n$ rounds, for any $ 4$ contestants, non of them has played with the others or there have been at least $ 2$ games played within those $ 4$.
Problem
Source: China TST 2002 Quiz
Tags: combinatorics unsolved, combinatorics
P-H-David-Clarence
20.10.2016 16:47
The answer is m-1
Akatsuki1010
21.11.2016 16:40
Any idea for this problem?
ThE-dArK-lOrD
04.12.2017 19:07
I'm not sure but I think the answer is $m-1$ for even $m$ and $m$ for odd $m$.
Pathological
29.10.2019 04:30
I think that the answer is always $m-1$. First let's construct this. For even $m$, label the people $A_1, A_2, A_3, \cdots, A_m, B_1, B_2, \cdots, B_m$ arbitrarily. For $1 \le i < m$, on day $i$, $A_j$ will play $A_{i + j}$ for each $1 \le j \le m$, where indices are modulo $m$. For day $m$, $A_j$ will play $B_j$ for $1 \le j \le m.$ For the last $m-1$ days, we simply schedule so that the $A_j$'s play each other once and the $B_j$'s play each other once. For odd $m$, label the people in the same way, and schedule games in the same way for the first $m-1$ days. For the $(m-1+i)$th day, for $1 \le i \le m$, we will have $A_i$ play $B_i$. Then, we pair up the remaining players so that $A_x$ plays $A_{2i - x}$, $B_x$ plays $B_{2i - x}$, for $x \neq i$, where indices are again modulo $m.$ In this way, we've shown that $m-1$ always works. Suppose now that $n \le m-2$ worked. Consider the graph where we connect two people iff they have played in the first $n$ days. This graph is clearly $n-$regular. Consider the largest set $S$ of people, none of whom have played each other. Suppose $|S| = k$. By Turan's Theorem, it's easy to see that $k \ge 3.$ Note that if anybody else plays at most $k-2$ of the people in $S$, then we can find a $4-$tuple with exactly one match played among them. Hence, suppose that everyone else plays at least $k-1$ of the people in $S$. This implies that, because each of the people in $S$ plays $n$ others, there are at least $\frac{nk}{k-1}$ other people. Hence $k + \frac{nk}{k-1} \ge 2m.$ After simplifying, this is equivalent to $k^2 - (2m+1-n)k + 2n \ge 0.$ As $n \le m-2$, this implies that $k \ge 2m-n.$ This implies that since there are at most $n$ people not in $S$, we have $|S| = 2m-n$ and everybody in $S$ must play all of the people not in $S$. However, this means that anybody not in $S$ has played each of the $2m-n > n$ people in $S$, contradiction. So $n \le m-2$ do not work, and the answer is $\boxed{m-1}.$ $\square$