Kvant Math Problem 983
The tournament is a complete directed graph on $16$ vertices.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m08s
Source on kvant.digital
Problem
In a tournament involving 16 tennis players, every pair of players plays one game.
- Give an example of a distribution of game results such that any 10 participants can be arranged in a circle so that each player has defeated the player to their left.
- Prove that if the condition in part (a) is satisfied, then any 11 participants can also be arranged in a circle in this way.
K. P. Kokhasy̆a
Exploration
The tournament is a complete directed graph on $16$ vertices. A set of players can be arranged in a circle so that each player defeated the player to their left precisely when the subtournament on those players contains a directed Hamiltonian cycle.
Part (a) asks for a tournament on $16$ vertices such that every $10$-vertex subtournament contains a Hamiltonian cycle. A natural source is a highly symmetric regular tournament. The cyclic tournament on $16$ vertices, where $i$ defeats $j$ whenever $j-i\pmod{16}\in{1,2,\dots,8}$, has strong connectivity properties. One expects every sufficiently large subset to contain a Hamiltonian cycle.
A simpler route is to use a transitive decomposition. If the vertices are divided into two groups of $8$, all games between the groups directed from the first group to the second, then any $10$-set containing at least $6$ vertices from one side inherits much structure. This does not seem likely to satisfy the condition.
The statement of part (b) suggests a sharp threshold phenomenon. If every $10$-vertex subtournament has a Hamiltonian cycle, then every $10$-vertex subtournament is strongly connected, because a directed cycle through all vertices lies in one strongly connected component. The problem may therefore reduce to a statement about strong connectivity.
Suppose the tournament is not strongly connected on some $11$-set $S$. Then the condensation of a tournament is transitive. Hence $S$ can be partitioned into nonempty sets $A,B$ with every edge directed from $A$ to $B$. Since $|S|=11$, one of $A,B$ has at least $10$ vertices. If $|A|\ge10$, choose $10$ vertices of $A$. Their subtournament cannot contain a Hamiltonian cycle that uses a vertex of $B$, and all its vertices lie in $A$. This does not yet contradict anything. A better counting argument is needed.
Let $S=A\cup B$ with all edges from $A$ to $B$. Since $|A|+|B|=11$, one side has at least $10$ only when the other side has size $1$. The dangerous case is $|A|=10$, $|B|=1$. Then the $10$-set $A$ itself would have to contain a Hamiltonian cycle. That is possible. So non-strong connectivity alone is insufficient.
A stronger observation: if an $11$-vertex subtournament lacks a Hamiltonian cycle, then by Camion's theorem it is not strongly connected. Thus there exists a partition $A,B$ with all edges from $A$ to $B$. Since both parts are nonempty and $|A|+|B|=11$, one of them has size at least $6$. Suppose $|A|\ge6$. Choose all vertices of $B$ and enough vertices of $A$ to obtain $10$ vertices. Because every edge between the chosen vertices from different parts still goes from $A$ to $B$, this $10$-vertex subtournament is not strongly connected, hence cannot contain a Hamiltonian cycle. That contradicts the hypothesis. This is the key argument.
For part (a), a regular cyclic tournament should work. The relevant theorem is that every strongly connected tournament contains a Hamiltonian cycle. Thus it suffices to construct a tournament in which every $10$-vertex subtournament is strongly connected. In the cyclic tournament on $16$ vertices, every vertex has out-neighbors at cyclic distances $1,\dots,8$. If a subset $X$ of at least $9$ vertices were not strongly connected, there would be a partition $X=A\cup B$ with all edges from $A$ to $B$. Taking consecutive representatives around the circle should force $|A|+|B|\le8$. More concretely, if $a\in A$, then the next eight vertices cyclically after $a$ cannot belong to $A$, otherwise some edge would point the wrong way. Hence between any two vertices of $A$ there are at least eight cyclic steps. Therefore $|A|\le2$. Symmetrically $|B|\le2$. Hence a disconnected subset has size at most $4$, impossible for size $10$. This yields the desired example.
The crucial point is proving that every $10$-vertex subtournament of the cyclic tournament is strongly connected.
Problem Understanding
We represent the tournament by a directed graph whose vertices are the players and whose directed edges point from the winner to the loser.
A set of players can be arranged in a circle so that each player defeated the player to their left exactly when the subtournament induced by those players contains a directed Hamiltonian cycle.
Part (a) asks for an explicit tournament on $16$ vertices such that every induced subtournament on $10$ vertices has a directed Hamiltonian cycle.
Part (b) asks us to prove that any tournament satisfying the condition from part (a) automatically has the stronger property that every induced subtournament on $11$ vertices also has a directed Hamiltonian cycle.
This is a Type B problem. The main difficulty is to convert the condition on all $10$-vertex subtournaments into a structural statement about strong connectivity and then show that an $11$-vertex counterexample would force a $10$-vertex counterexample.
Proof Architecture
The first lemma states that every strongly connected tournament contains a directed Hamiltonian cycle; this is Camion's theorem.
The second lemma states that in the cyclic tournament on $16$ vertices, every induced subtournament on at least $9$ vertices is strongly connected; the proof uses the cyclic ordering and shows that any decomposition $A\to B$ forces both $A$ and $B$ to have size at most $4$.
Using these lemmas, part (a) follows because every $10$-vertex subtournament of the cyclic tournament is strongly connected and therefore contains a Hamiltonian cycle.
For part (b), assume some $11$-vertex subtournament has no Hamiltonian cycle. By Camion's theorem it is not strongly connected. A decomposition $A\to B$ then exists. Since $|A|+|B|=11$, one part has at least $6$ vertices. Selecting all vertices of the smaller part and enough vertices of the larger part gives a $10$-vertex subtournament that is still not strongly connected, contradicting the hypothesis.
The hardest point is the proof that every large subset of the cyclic tournament is strongly connected.
Solution
Label the players by the residues modulo $16$:
$$0,1,\dots,15.$$
Define a tournament $T$ by declaring that $i$ defeats $j$ whenever
$$j-i \pmod{16}\in{1,2,\dots,8}.$$
This is the regular cyclic tournament on $16$ vertices.
We first prove that every induced subtournament of $T$ on at least $9$ vertices is strongly connected.
Assume the contrary. Let $X$ be a subset of vertices with $|X|\ge9$ such that the subtournament $T[X]$ is not strongly connected. Then there exist nonempty sets $A,B$ partitioning $X$ with every edge between them directed from $A$ to $B$.
Write the vertices around the circle in cyclic order. Take two distinct vertices $a,a'\in A$. If the cyclic distance from $a$ to $a'$ is at most $8$, then by the definition of the tournament, $a$ defeats $a'$. Interchanging the roles of $a$ and $a'$, one of the two vertices defeats the other. Since all edges from $A$ to $B$ go in the same direction, any vertex of $B$ lying on the shorter arc between $a$ and $a'$ would create an edge directed from $B$ to $A$, which is impossible. Hence between consecutive vertices of $A$ in the cyclic order there must be at least one block of eight consecutive positions containing no vertex of $A$.
Consequently each vertex of $A$ excludes the next eight cyclic positions from belonging to $A$. Since there are only $16$ positions altogether, we obtain
$$|A|\le4.$$
The same argument applied to $B$ gives
$$|B|\le4.$$
Therefore
$$|X|=|A|+|B|\le8,$$
contrary to $|X|\ge9$.
Hence every induced subtournament of $T$ on at least $9$ vertices is strongly connected.
Camion's theorem states that every strongly connected tournament contains a directed Hamiltonian cycle. Every $10$-vertex subtournament of $T$ is strongly connected, so every such subtournament contains a directed Hamiltonian cycle. This gives the required example for part (a).
Now assume a tournament on $16$ vertices has the property that every $10$-vertex subtournament contains a directed Hamiltonian cycle.
Suppose that some $11$-vertex subtournament $S$ does not contain a directed Hamiltonian cycle. By Camion's theorem, $S$ is not strongly connected. Hence there exist nonempty sets $A,B$ partitioning the vertices of $S$ such that every edge between them is directed from $A$ to $B$.
Since
$$|A|+|B|=11,$$
one of the two sets has at least $6$ vertices. Assume $|A|\ge6$.
Choose all vertices of $B$ and choose $10-|B|$ vertices from $A$. This is possible because
$$10-|B| \le |A|-1 < |A|.$$
Let $Y$ be the resulting set of $10$ vertices.
The subtournament $S[Y]$ still has the property that every edge between $A\cap Y$ and $B$ is directed from $A\cap Y$ to $B$. Both parts are nonempty, because $B\neq\varnothing$ and $10-|B|\ge1$. Therefore $S[Y]$ is not strongly connected.
A tournament containing a directed Hamiltonian cycle is strongly connected. Hence $S[Y]$ cannot contain a directed Hamiltonian cycle. This contradicts the assumption that every $10$-vertex subtournament does contain one.
The contradiction shows that every $11$-vertex subtournament must contain a directed Hamiltonian cycle.
This completes the proof.
∎
Verification of Key Steps
The most delicate step in part (a) is the estimate $|A|\le4$. Re-deriving it directly, if $a\in A$, then the next eight vertices in cyclic order cannot belong to $A$. Indeed, if one of them did, the orientation rule would force an edge whose direction is incompatible with the decomposition $A\to B$. Thus distinct vertices of $A$ must be separated by at least four positions on average around a cycle of length $16$, which yields $|A|\le4$. Applying the same reasoning to $B$ gives $|B|\le4$.
The critical step in part (b) is constructing a $10$-vertex subtournament that remains disconnected. If $|A|=6$ and $|B|=5$, the construction chooses all five vertices of $B$ and five of the six vertices of $A$. Both sides remain nonempty, and all cross edges still point from the chosen vertices of $A$ toward $B$. Hence the induced subtournament is still not strongly connected. The same argument works for every split with $|A|+|B|=11$.
Another point where a mistake can occur is the use of Camion's theorem. The theorem is applied in both directions needed here. A strongly connected tournament has a Hamiltonian cycle. Contrapositively, if a tournament has no Hamiltonian cycle, it is not strongly connected. Both uses are legitimate.
Alternative Approaches
Instead of the cyclic tournament, one may use any regular circulant tournament on $16$ vertices and prove directly that every induced subtournament on at least $9$ vertices is strongly connected. The argument is essentially the same but can be phrased in terms of domination intervals rather than cyclic distances.
Part (b) can also be formulated through the condensation digraph of a tournament. If an $11$-vertex subtournament lacks a Hamiltonian cycle, its condensation has at least two vertices and is a transitive tournament. Taking all vertices from one terminal component and enough vertices from the adjacent component immediately produces a $10$-vertex subtournament whose condensation is still nontrivial. The proof given above is preferable because it avoids introducing the full condensation machinery and works directly with the partition $A\to B$.