$n$ teams take part in a tournament, in which every two teams compete exactly once, and that no draws are possible. It is known that for any two teams, there exists another team which defeated both of the two teams. Find all $n$ for which this is possible.
Problem
Source: Taiwan 1st TST 2005, final exam, first day, problem 3
Tags: linear algebra, matrix, quadratics, combinatorics proposed, combinatorics
13.08.2005 03:22
I hope you have a "smarter" solution. First notice that if it's possible for $n$, then it's possible for $n+1$: perform the construction for $n$, and add another team which everyone defeates, getting a construction for $n+1$. This means that all we need to find is the minimal $n$ for which it works. Then I showed it's impossible for $n=6$. This isn't hard at all, since the steps one has to make while trying to construct such a graph are pretty limited, but I won't write it here, since it's boring. After that, I just sort of "stumbled upon" a construction for $7$. I'll just write the adjacency matrix of a tournament with $n=7$ here: a $1$ in position $(i,j)$ means that $i$ defeated $j$. \[\begin{pmatrix}0&1&0&0&0&1&1\\0&0&0&1&1&0&1\\1&1&0&0&1&0&0\\1&0&1&0&0&0&1\\1&0&0&1&0&1&0\\0&1&1&1&0&0&0\\0&0&1&0&1&1&0\end{pmatrix}\]
13.08.2005 03:39
This problem was also posted in a topic called smallest number. There we put the n = 7 example in a broader context (quadratic residues).
13.08.2005 09:50
actually for $n$ odd, $n\geq 7$ there is a simple(elementary) description for such a graph. label the vertices by $0,1,\ldots,2n$. i shall just write down (some of) the vertices which correspond to defeats alone(i.e. when I write $j$ along the row labelled $i$ i mean that $i$ defeated $j$): $0:1,2,\ldots,2n;\\ 1:n,n+2,n+3,\ldots,2n;\text{(n+1 missing)}\\ 2:1,n+1,n+3,\ldots,2n;\text{(n+2 missing)}\\ \\ n:n-1,n+1,n+2,\ldots,2n-1;\text{(2n missing)}\\ \\ n+1: 0,1,n+2\\ n+2: 0,2,n+3\\ \\ 2n: 0,n,n+1$ to explain what is written here, for instance the first row simply means that $0$ defeats $1,2,\ldots,n$ and so on. note that this is a proper description of a partial tournament because if $j$ lies on row labelled $i$ then $i$ does not lie on row $j$. of course this is not the description of a tournament completely but what we need is the following: basically notice that $n+1$ defeats $1$ but all the higher numbered players lose to $1$. similarly $n+2$ defeats $2$ but all the other players among $n+1,\ldots,2n$ lose to $2$, and so on. once this is the situation, notice that in this partial tournament(i.e at this stage of the tournament), for any unordered pair, they are already in some row. to see this easily notice that any pair of the form $(0,k)$ occurs amonst the last $n$ rows. now any pair $(i,j)$ with both $i,j\in\{1,2,\ldots,n\}$ occurs from the first row. now if $i\leq n,j>n$ then the pair $(i,j)$ occurs amongst the first $n$ rows unless the pairs are one of $(1,n+2),(2,n+3),\ldots,(n-1,2n),(n,n+1)$ and these occur amongst the last $n$ rows. finally if both $i,j>n$ then they occur(actually they occur $n-1$ times) amongst the first $n$ rows and so that completes our requirements. as remarked before, what remains to be played are some of those games amongst $1,2\ldots,n$ and some amongst $n+1,n+2,\ldots,2n$.but their results are irrelevant. grobber's solution for $n=7$ is also obtained from this.in that case since such a diagram describes $3$ losses for each player, it turns out that the above described tournament in that case is complete.