Kvant Math Problem 819

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m22s
Source on kvant.digital

Problem

In Shvambrania there are $n$ cities, every two of which are connected by a road. (Roads intersect only at cities, and all intersections are arranged at different levels.) An evil wizard intends to assign a one-way direction to each road in such a way that, after leaving any city, it is impossible to return to it. Prove that:

1. the wizard can do this;
2. in this case there exists a city from which one can reach all other cities, and a city from which one cannot leave;
3. there exist $n!=1\cdot2\cdot\ldots\cdot n$ ways to carry out the evil wizard’s intention.

L. M. Kogan

Exploration

We are given the complete graph on $n$ vertices with each edge oriented in exactly one direction. The condition says that after departing from any city, it is impossible to return to it, which is equivalent to the absence of any directed cycle in the resulting orientation.

A natural first attempt is to test small cases. For $n=1$ and $n=2$, any orientation works. For $n=3$, if we try to avoid cycles, we quickly see that any directed cycle $a \to b \to c \to a$ must be forbidden, so the only allowed orientations are those that “flow in one direction” along some ordering of the vertices. This suggests that a global linear order of cities should underlie every valid configuration.

If we assume such an order exists, say $1,2,\dots,n$, then directing every edge from smaller to larger clearly prevents cycles. Conversely, if no cycle exists, it should be possible to rank vertices so that all edges point forward. The key issue is to justify rigorously that acyclicity forces such a total order and that this order is unique.

Once such an order is established, the second statement about existence of a city that reaches all others and a city that cannot leave becomes transparent: the first element of the order has only outgoing edges, and the last has only incoming edges.

The most delicate point is counting: we must ensure that every acyclic orientation corresponds to exactly one ordering and vice versa, with no overcounting or hidden symmetries.

Problem Understanding

This is a Type A classification problem. We must describe all orientations of the complete graph on $n$ vertices that contain no directed cycle and prove both existence and uniqueness properties, as well as count them.

The expected structure is that such orientations correspond exactly to total orders of the vertices, where each edge is directed from earlier to later in the order. This would immediately imply the existence of a source and a sink and give a count of $n!$.

The core difficulty is proving that every acyclic orientation of a complete graph induces a unique linear ordering.

Proof Architecture

First, construct an explicit acyclic orientation from any permutation of the $n$ cities by directing edges consistently with the permutation, and prove this produces no directed cycles.

Second, prove that in any acyclic orientation of a complete graph, one can define a relation $u \prec v$ if the edge is directed $u \to v$, and show that this relation is transitive and total, hence defines a strict linear order of all vertices.

Third, prove that this order is unique and that the original orientation is recovered by directing edges according to it.

Fourth, deduce that the first element in the order is a city from which all others are reachable, and the last is a city from which none can be left.

Fifth, establish a bijection between acyclic orientations and permutations, yielding the count $n!$.

The most delicate lemma is the transitivity argument, since it must rule out hidden indirect configurations that could otherwise violate linearity.

Solution

Let the cities be vertices of the complete graph $K_n$, and each road is oriented in exactly one direction. The condition that after leaving any city it is impossible to return to it is equivalent to the absence of any directed cycle.

We first construct a family of orientations satisfying this condition. Let $\sigma$ be any permutation of the cities. Label the cities as $v_{\sigma(1)}, v_{\sigma(2)}, \dots, v_{\sigma(n)}$. For any pair $i<j$, direct the road between $v_{\sigma(i)}$ and $v_{\sigma(j)}$ from $v_{\sigma(i)}$ to $v_{\sigma(j)}$.

In this orientation, any directed path strictly increases the index in the permutation. Hence it is impossible to return to a previously visited city, since that would require a strictly decreasing sequence of indices along a directed cycle, which is impossible. This proves existence.

We now show that any acyclic orientation must arise in this way. Consider any such orientation and define a relation on cities by writing $u \prec v$ if and only if the road between $u$ and $v$ is directed from $u$ to $v$.

For any two distinct cities $u$ and $v$, exactly one of $u \prec v$ or $v \prec u$ holds, since every pair is connected by exactly one directed edge. Thus the relation is total.

We prove transitivity. Suppose $u \prec v$ and $v \prec w$. If it were not true that $u \prec w$, then we would have $w \prec u$. Then the directed edges would form a cycle

$u \to v \to w \to u,$

contradicting acyclicity. Hence $u \prec w$, and the relation is transitive.

Thus $\prec$ is a strict total order on the set of cities. Therefore there exists a unique ordering of the cities

$v_1 \prec v_2 \prec \cdots \prec v_n.$

By construction, every edge is directed from $v_i$ to $v_j$ whenever $i<j$. In particular, the city $v_1$ has all incident edges directed outward, so from it one can reach every other city in a single step, hence also by paths of arbitrary length. The city $v_n$ has all incident edges directed inward, so no road allows one to leave it.

This proves statement 2.

We now count all valid orientations. Given any permutation of the $n$ cities, the construction above produces a valid orientation. Conversely, any valid orientation defines a strict total order of the cities, hence determines a unique permutation by listing cities in increasing order with respect to $\prec$. These two procedures are inverse to each other, so there is a bijection between valid orientations and permutations of $n$ elements. Therefore the number of such orientations is $n!$.

Thus all three statements are established.

Verification of Key Steps

The critical point in the argument is the transitivity of the relation $\prec$. The only nontrivial configuration arises when $u \prec v$ and $v \prec w$, since the edge between $u$ and $w$ must be oriented one way or the other. If it were oriented $w \to u$, then the three directed edges $u \to v$, $v \to w$, and $w \to u$ form a directed cycle of length $3$, which contradicts the assumption that no directed cycle exists. Since every pair is connected by exactly one directed edge, no alternative possibility remains, and thus $u \prec w$ must hold.

The second delicate point is the bijection. Injectivity follows because the order is uniquely determined by the orientation: the minimal element with respect to $\prec$ is uniquely defined as the vertex with no incoming edges, and removing it reduces the problem to a smaller complete graph while preserving acyclicity, forcing a unique recursive reconstruction of the ordering. Surjectivity follows from the explicit construction using permutations. No two different permutations yield the same orientation, since if two permutations differ, there exist two consecutive vertices whose relative order differs, producing an edge whose direction differs as well.

Alternative Approaches

An alternative proof uses induction on $n$ by repeatedly removing a vertex of minimal in-degree, which must exist in any finite acyclic orientation. One shows that this vertex is unique and must be the first in the linear order, then removes it and applies the argument to the remaining complete graph. This produces the same bijection with permutations but emphasizes constructive elimination rather than global transitivity.