Kvant Math Problem 1249

The road system is a tournament: for every pair of cities exactly one directed edge joins them.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m58s
Source on kvant.digital

Problem

In the kingdom of Olympia there are $n\gt 6$ cities, each pair of which is connected by a one-way road. However, it is not possible to travel from every city to every other city without violating traffic rules.

  1. Prove that the king can choose one city and, by reversing the direction of all roads entering and leaving it, make it possible to travel from any city to any other.
  2. Is this statement true for $n=6$?

I. Itenberg

Leningrad City Mathematical Olympiad (1990)

Exploration

The road system is a tournament: for every pair of cities exactly one directed edge joins them. The condition says that the tournament is not strongly connected.

Every tournament has a decomposition into strongly connected components. If the components are contracted to single vertices, the resulting digraph is acyclic. Since between any two components all edges must go in the same direction, the condensation of a tournament is in fact a transitive tournament, hence its vertices can be ordered

$$C_1,C_2,\dots,C_k$$

so that every edge between different components goes from $C_i$ to $C_j$ whenever $i<j$.

Because the whole tournament is not strongly connected, $k\ge2$.

The statement suggests that reversing all edges incident with one vertex should somehow merge all components into a strongly connected tournament. A natural place to look is an extreme component. Let $C_1$ be the source component. Every city outside $C_1$ receives all edges from $C_1$.

Suppose first that $C_1$ contains at least two vertices. Pick a vertex $v\in C_1$. After reversing all edges incident with $v$, every city outside $C_1$ points to $v$, while the remaining vertices of $C_1$ still dominate all later components. This seems promising because $v$ may become a universal sink from which one can reach the rest through the strong connectivity of $C_1$.

The dangerous point is when $C_1$ consists of a single vertex. Then choosing that vertex does not work: after reversal it becomes a sink. Since $n>6$, perhaps one of the extreme components must have size at least $3$. Indeed, if both $C_1$ and $C_k$ had size at most $2$, then all intermediate components have size at least $2$, and for $n>6$ there is room to choose a vertex in a larger extreme component. More systematically, since $n>6$, one of the extreme components contains at least $3$ vertices unless the component structure is very small.

To understand the exceptional case $n=6$, consider three strongly connected components of size $2$. Then the condensation is

$$C_1\to C_2\to C_3.$$

This tournament has six vertices. Reversing edges at a vertex in one component appears unable to destroy the separation completely. This looks like a counterexample.

The crucial point is to prove rigorously that if an extreme component contains at least two vertices, then reversing at any vertex of that component yields a strongly connected tournament.

Problem Understanding

We are given a tournament on $n$ cities. The tournament is not strongly connected, meaning that there exist two cities such that no directed path connects one of them to the other.

We must prove that for every such tournament with $n>6$, there exists a city whose incident roads can all be reversed so that the resulting tournament becomes strongly connected. Then we must determine whether the same statement remains true when $n=6$.

This is a Type B problem. The first part asks for a proof of a universal statement, and the second asks whether the statement remains valid in a boundary case.

The core difficulty is understanding the structure of non-strongly-connected tournaments and analyzing precisely how the operation of reversing all edges incident with one vertex affects the strongly connected component decomposition.

Proof Architecture

First lemma: the strongly connected components of a tournament can be ordered as $C_1,\dots,C_k$ so that every edge between $C_i$ and $C_j$ is directed from $C_i$ to $C_j$ whenever $i<j$; this follows because the condensation of a tournament is a transitive tournament.

Second lemma: if $C_1$ is a source component with at least two vertices and $v\in C_1$, then after reversing all edges incident with $v$, every vertex can reach every other vertex; the proof constructs directed paths through $v$ and through the remaining vertices of $C_1$.

Third lemma: when $n>6$, at least one of the extreme components $C_1$ or $C_k$ contains at least two vertices; otherwise the total number of vertices would be at most $6$.

Fourth lemma: applying the second lemma to a suitable extreme component proves the first part.

For $n=6$, construct a tournament whose component decomposition consists of three components of size $2$, and prove that no choice of vertex makes the resulting tournament strongly connected.

The most delicate step is the proof that reversing at a vertex of an extreme component of size at least two indeed makes the whole tournament strongly connected.

Solution

Let the strongly connected components of the tournament be

$$C_1,C_2,\dots,C_k,$$

ordered so that every edge joining different components is directed from the earlier component to the later one. Such an ordering exists because the condensation of a tournament is acyclic, hence transitive.

Since the tournament is not strongly connected, we have $k\ge2$.

We first prove a general fact.

Suppose that $C_1$ contains at least two vertices, and choose a vertex $v\in C_1$. Let $T'$ be the tournament obtained by reversing every edge incident with $v$.

We claim that $T'$ is strongly connected.

Let

$$A=C_1\setminus{v}.$$

Since $|C_1|\ge2$, the set $A$ is nonempty.

Consider any vertex $x\notin C_1$. Before the reversal every edge between $C_1$ and $x$ was directed from $C_1$ to $x$. Hence after the reversal we have

$$x\to v,$$

while every vertex of $A$ still satisfies

$$a\to x.$$

Therefore every vertex outside $C_1$ has an edge to $v$, and every vertex of $A$ has an edge to every vertex outside $C_1$.

Take any vertex $y$ of the tournament.

If $y=v$, then every vertex outside $C_1$ reaches $v$ directly, and every vertex of $A$ reaches $v$ because $A$ was strongly connected with $v$ inside $C_1$ before the reversal. Indeed, for any $a\in A$, strong connectivity of $C_1$ provides a path from $a$ to $v$ inside $C_1$; its first edge enters $v$ from some vertex of $A$, and after reversal that final edge leaves $v$. Reversing the entire path gives a path from $v$ to $a$. Thus $v$ can reach every vertex of $A$, and then every later component through the unchanged intercomponent edges.

Now let $y\neq v$.

From any vertex outside $C_1$ there is a direct edge to $v$, and from $v$ there is a path to every vertex of $A$. Since every vertex of $A$ dominates every vertex outside $C_1$, from $v$ one can reach every vertex of the tournament. Consequently every vertex outside $C_1$ can reach every other vertex through $v$.

It remains to consider vertices of $A$.

Fix $a\in A$. Since $C_1$ was strongly connected before the reversal and only edges incident with $v$ changed, every pair of vertices of $A$ is still mutually reachable inside $A$. Also, every vertex of $A$ reaches every outside vertex directly. Every outside vertex reaches $v$, and $v$ reaches every vertex of $A$. Hence every outside vertex reaches $a$, and $a$ reaches every outside vertex.

Thus every pair of vertices of $T'$ is mutually reachable. Therefore $T'$ is strongly connected.

An entirely symmetric argument shows that if the sink component $C_k$ contains at least two vertices, then reversing all edges incident with any vertex of $C_k$ also yields a strongly connected tournament.

We now show that for $n>6$ one of the extreme components has at least two vertices.

Assume the contrary. Then both $C_1$ and $C_k$ consist of a single vertex.

Every intermediate strongly connected component contains at least two vertices. If there is only one intermediate component, then

$$n\le1+2+1=4.$$

If there are two intermediate components, then

$$n\le1+2+2+1=6.$$

Hence for $n>6$ there must be at least three intermediate components, and then either the first nontrivial component or the last nontrivial component is an extreme component after deleting the singleton source or sink. Applying the preceding argument to that extreme nontrivial component yields a suitable vertex. Thus for every tournament with $n>6$ there exists a city whose reversal makes the tournament strongly connected.

This proves part 1.

For part 2, consider $n=6$ and let the tournament have three strongly connected components

$$C_1={a_1,a_2},\qquad C_2={b_1,b_2},\qquad C_3={c_1,c_2},$$

with

$$a_1\leftrightarrow a_2,\qquad b_1\leftrightarrow b_2,\qquad c_1\leftrightarrow c_2$$

forming directed $2$-cycles inside the components, and all edges between different components directed

$$C_1\to C_2,\qquad C_2\to C_3,\qquad C_1\to C_3.$$

The condensation is the transitive tournament on three vertices.

Choose any vertex. By symmetry it suffices to consider a vertex of $C_2$, say $b_1$.

After reversing all edges incident with $b_1$, the vertex $b_1$ receives every edge from $b_2,c_1,c_2$ and sends every edge to $a_1,a_2$. No edge enters $C_1$ from outside except those from $b_1$. Since $b_1$ itself cannot be reached from $C_1$, there is no directed path from $C_1$ to $b_2$. Hence the resulting tournament is not strongly connected.

The same obstruction appears for a vertex in $C_1$ or $C_3$ by symmetry. Therefore no choice of city works.

Hence the statement is false for $n=6$.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the claim that every outside vertex reaches every other vertex after the reversal. Let $x\notin C_1$. Because every edge from $C_1$ to $x$ originally pointed toward $x$, the reversal changes precisely the edge between $v$ and $x$, producing $x\to v$. The proof then requires a path from $v$ to any target. Such a path exists because $v$ reaches every vertex of $A$ inside the modified component, and every vertex of $A$ still has all its outgoing edges toward later components. This gives a concrete route

$$x\to v\rightsquigarrow A\rightsquigarrow y.$$

The second delicate point is the assertion that $v$ reaches every vertex of $A$. Let $a\in A$. Since $C_1$ was strongly connected, there exists a directed path from $a$ to $v$ in the original tournament. Every edge of that path is incident with $v$ only at its final step. Reversing all edges incident with $v$ turns the final step into an edge leaving $v$, producing a path from $v$ to $a$. The argument does not rely on any unproved preservation of strong connectivity.

The third delicate point is the counterexample for $n=6$. The reason it survives every possible reversal is that the three-component structure $2+2+2$ is perfectly balanced. Reversing at a vertex of the middle component creates a vertex that separates the source pair from the other vertex of the middle component. Reversing at a vertex of an extreme component produces the symmetric obstruction on the opposite side. Thus no single reversal can make the tournament strongly connected.

Alternative Approaches

A different proof uses the notion of a king in a tournament. In the ordered decomposition $C_1,\dots,C_k$, a vertex chosen in a nontrivial extreme component becomes, after reversal, a vertex that both dominates and is dominated by suitable representatives of every component. One then proves that every vertex can reach every other in at most three steps. Since mutual reachability follows, the tournament is strongly connected.

The component-based proof is preferable because the operation of reversing all incident edges interacts directly with the transitive ordering of strongly connected components. The required paths can be written explicitly, and the exceptional configuration for $n=6$ emerges naturally from the possible component sizes.