In a competition there are $18$ teams and in each round $18$ teams are divided into $9$ pairs where the $9$ matches are played coincidentally. There are $17$ rounds, so that each pair of teams play each other exactly once. After $n$ rounds, there always exists $4$ teams such that there was exactly one match played between these teams in those $n$ rounds. Find the maximum value of $n$.
Problem
Source: 2002 China National Olmpiad
Tags: graph theory, combinatorics proposed, combinatorics
28.02.2013 14:52
at first we prove that there is a $14$-regular graph $G$. ( $\left | G \right |=18 , \forall v\in G,deg (v)=14$ for which there is some $R\subset G$ such that $\left | R \right |=4$ and it has exactly one edge. by Havel-Hakimi theorem (can you see it http://en.wikipedia.org/wiki/Degree_(graph_theory)) we will prove that there is such graph. let $L=G/\left \{ u,v \right \}$ (note $u,v\in R ,deg_{R}(u)=0,deg_{R}(v)=0$). by use of Havel we have $d_{G/L}=(16,16,14,14,...,14)=(3,3,3,...3,1,1)=(3,3,..,3,2,2,..,1,1)=(2,2,..,2,1,1,..,1)=(1,1,1,1,1,1,1,1,0)$ so that is graphitty and there is such graph. now we know that $\chi {}'(K_{2n})=2n-1\Rightarrow \chi {}'(K_{18})=17$ .we removed the edges by colors of $17,16,15$ .so we colored the edges of $G$ by 14 colors and there are no two edges by same color.(let the edge of $R$ be $1$). now we have $f$ is connect to $g$ by color $t$ if and only if $f$ has competition by $g$ in round $t$ . so $n=14$. (its obvious that $n$ can not exceed to $14$.)
20.10.2019 23:10
I think we need to show that all such graphs have some $R \subset G$ with $|R| = 4$ and only one edge, not that there exists some such graph. Hence, I believe that the answer is $\boxed{7}$ and not $14.$ We claim that the answer is $7.$ First, let's show that $n = 7$ actually works. Consider the largest group $G$ of people, none of whom have played each other. It's easy to see that $|G| \ge 3$, by Zarankiewicz's Lemma, say. Suppose that $|G| = k.$ Notice that if there exists some other person not in $G$ who played with at most $k-2$ people in $G$, then we win. Hence, since everybody else must play somebody in $G$ (else we could add that person to expand $G$), there are at most $\frac{k \cdot 7}{k-1}$ other people. Therefore $k + \frac{7k}{k-1} \ge 18$, which gives $k \ge 10.$ However, this is clearly absurd, because nobody else can possibly have played with $9$ people already. Hence, $n = 7$ works. Let's now show that $n > 7$ do not work. When $n = 8$, we will construct as follows. Label the people $A_1, A_2, A_3, \cdots, A_9, B_1, B_2, \cdots, B_9.$ On day $i$, $A_x$ will play $B_{x+i}$ for each $1 \le x \le 8$, where indices are modulo $9.$ It's easy to see how to assign matches for the other days, so it remains to check that no four people with exactly one match played between them exists. This is easy to check though. Now, for $n = 9$, consider the complement of the graph described above for $n = 8.$ It's easy to see that any four people will have played at least two matches between them. For $n \ge 10$, just add match days to the graph for $n = 9$, and clearly any four people will have still played at least two matches between them. Hence, $n \ge 8$ all do not work, and the answer is $n = \boxed{7}.$ $\square$
06.07.2023 15:18
A graph to prove $n=7$ can take.