Kvant Math Problem 211

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m33s
Source on kvant.digital

Problem

Given $n$ points, $n \gt 4$. Prove that it is possible to connect them with arrows so that from each point to any other one, it is possible to reach it by following either one arrow or two arrows (each pair of points can be connected by an arrow in only one direction; one can travel along an arrow only in the indicated direction).

G. Sh. Friedman

All-Union Mathematical Olympiad for School Students (VII, 8th grade)

Exploration

The problem asks for an orientation of all edges between $n$ points. In graph-theoretic language, we must orient the complete graph $K_n$ so that for every ordered pair of distinct vertices $(A,B)$, there is a directed path from $A$ to $B$ of length at most $2$.

Trying small cases is useful. For $n=5$, place the vertices on a circle and orient every edge from a vertex to the next two vertices in the clockwise order. Label the vertices $0,1,2,3,4$ modulo $5$. Then $0$ points to $1$ and $2$, $1$ points to $2$ and $3$, and so on. From $0$ to $3$ there is a path $0\to1\to3$, and from $0$ to $4$ there is a direct arrow. Similar checks work for all pairs.

This suggests using a cyclic arrangement for general $n$. Let the vertices be $0,1,\dots,n-1$ around a circle. For each pair, orient the edge in the clockwise direction whenever the clockwise distance is at most half the circle. If $n$ is odd, every pair has a unique shorter direction around the circle. If $n$ is even, pairs of opposite vertices require a special convention.

The main question is whether every missing direct arrow can be replaced by a two-step path. Suppose $n=2m+1$ is odd. Then each vertex sends arrows to the next $m$ vertices clockwise. If $j-i$ modulo $n$ equals $d>m$, there is no direct arrow from $i$ to $j$. Writing $d=m+r$ with $1\le r\le m$, the intermediate vertex $i+r$ seems promising. Indeed, $i\to i+r$ because $r\le m$, and $(j-(i+r))\equiv m\pmod n$, so $i+r\to j$.

For even $n=2m$, orient every edge toward the vertex reached within fewer than $m$ clockwise steps; for opposite pairs, orient consistently, say from $i$ to $i+m$ for $i=0,\dots,m-1$. The same idea should work, but opposite vertices require checking separately.

The step most likely to conceal an error is the verification that every nonadjacent ordered pair admits a suitable intermediate vertex in the even case, especially when the distance is exactly $m$.

Problem Understanding

We must show that for every integer $n>4$, there exists an orientation of the complete graph on $n$ vertices such that for any two distinct vertices $A$ and $B$, either there is a direct arrow $A\to B$, or there exists a vertex $C$ with $A\to C\to B$.

This is a Type D problem. We must construct an orientation explicitly and verify that every ordered pair of vertices is connected by a directed path of length at most $2$.

The core difficulty is to find a systematic orientation and then prove that every ordered pair not joined directly is joined through a suitable intermediate vertex.

Proof Architecture

Lemma 1. For odd $n=2m+1$, if the vertices are labeled modulo $n$ and each vertex $i$ sends arrows to $i+1,\dots,i+m$, then every ordered pair of distinct vertices is connected by a directed path of length at most $2$.

Sketch. If the clockwise distance from $i$ to $j$ is at most $m$, there is a direct arrow; otherwise write the distance as $m+r$ and use the intermediate vertex $i+r$.

Lemma 2. For even $n=2m$, if each vertex $i$ sends arrows to vertices at clockwise distances $1,\dots,m-1$, and opposite pairs are oriented from $i$ to $i+m$ for $i=0,\dots,m-1$, then every ordered pair of distinct vertices is connected by a directed path of length at most $2$.

Sketch. Distances less than $m$ give direct arrows. For distance $m$, use a carefully chosen intermediate vertex. For distance greater than $m$, write the distance as $m+r$ and again use $i+r$.

The hardest direction is Lemma 2, specifically the case of opposite vertices.

Solution

Arrange the $n$ points on a circle and label them by residues modulo $n$.

First consider the case $n=2m+1$, where $n$ is odd.

For two distinct vertices $i$ and $j$, let $d$ be the clockwise distance from $i$ to $j$, so $1\le d\le 2m$. Orient the edge between $i$ and $j$ as $i\to j$ whenever $1\le d\le m$.

Since $n$ is odd, exactly one of the two distances between $i$ and $j$ is at most $m$, so every edge receives exactly one direction.

Take any ordered pair of distinct vertices $(i,j)$.

If the clockwise distance $d$ from $i$ to $j$ satisfies $d\le m$, then by construction there is a direct arrow $i\to j$.

Assume now that $d>m$. Write

$$d=m+r, \qquad 1\le r\le m.$$

Let

$$k=i+r.$$

The clockwise distance from $i$ to $k$ equals $r$, hence $i\to k$.

Also,

$$j-k=(i+m+r)-(i+r)=m \pmod n.$$

Thus the clockwise distance from $k$ to $j$ equals $m$, so $k\to j$.

Hence

$$i\to k\to j.$$

Every ordered pair is therefore connected by a directed path of length at most $2$.

Now consider the case $n=2m$, where $n$ is even.

For two vertices whose clockwise distance is $d$ with $1\le d\le m-1$, orient the edge in the clockwise direction.

For each opposite pair ${i,i+m}$, where $i=0,1,\dots,m-1$, orient the edge as

$$i\to i+m.$$

Again every edge receives exactly one direction.

Take any ordered pair of distinct vertices $(i,j)$.

If the clockwise distance $d$ from $i$ to $j$ satisfies $d<m$, then there is a direct arrow $i\to j$.

Suppose next that $d=m$.

If $i\in{0,1,\dots,m-1}$, then by construction $i\to j$.

If $i\in{m,m+1,\dots,2m-1}$, then the opposite edge is directed from $j$ to $i$, not from $i$ to $j$. Set

$$k=i+1 \pmod n.$$

The clockwise distance from $i$ to $k$ is $1$, so $i\to k$.

The clockwise distance from $k$ to $j$ equals

$$m-1,$$

hence $k\to j$.

Therefore

$$i\to k\to j.$$

Finally, suppose $d>m$. Write

$$d=m+r, \qquad 1\le r\le m-1.$$

Let

$$k=i+r.$$

The clockwise distance from $i$ to $k$ is $r<m$, so $i\to k$.

Also,

$$j-k=(i+m+r)-(i+r)=m \pmod n.$$

Thus $k$ and $j$ are opposite vertices.

If $k\in{0,1,\dots,m-1}$, then the opposite edge is directed $k\to j$ by definition.

If $k\in{m,m+1,\dots,2m-1}$, replace the intermediate vertex by

$$k'=i+r+1.$$

The clockwise distance from $i$ to $k'$ is $r+1\le m$, and equality $r+1=m$ can occur only when $r=m-1$, in which case the edge is still directed from $i$ to $k'$ because $i$ and $k'$ form one of the prescribed opposite pairs. Hence $i\to k'$.

Furthermore,

$$j-k'=(m+r)-(r+1)=m-1,$$

so the clockwise distance from $k'$ to $j$ equals $m-1$, and therefore $k'\to j$.

Thus again there is a directed path of length $2$ from $i$ to $j$.

All ordered pairs of vertices are connected by a directed path of length at most $2$.

The required orientation exists for every $n>4$. This completes the proof.

∎

Verification of Key Steps

For odd $n=2m+1$, the crucial computation is the choice $k=i+r$ when the clockwise distance from $i$ to $j$ is $m+r$. The first edge exists because the distance from $i$ to $k$ is $r\le m$. The second edge exists because the distance from $k$ to $j$ is exactly $m$. Since every distance at most $m$ is oriented clockwise, $k\to j$ follows directly.

For even $n=2m$, opposite pairs require separate treatment. When the distance from $i$ to $j$ is exactly $m$ and the edge is oriented the wrong way, choosing $k=i+1$ gives distances $1$ and $m-1$. Both are strictly less than $m$, so both arrows point in the required directions. Without isolating this case, one could incorrectly assume that opposite vertices behave like the odd case.

In the case $d=m+r$ with $1\le r\le m-1$, the first choice $k=i+r$ may fail because the opposite edge between $k$ and $j$ could be oriented from $j$ to $k$. The correction $k'=i+r+1$ changes the second distance from $m$ to $m-1$, whose orientation is unambiguous. This is the point where a careless argument would most likely overlook the special convention for opposite vertices.

Alternative Approaches

A different construction uses a cyclic tournament when $n$ is odd and then derives the even case by inserting one additional vertex and orienting its incident edges appropriately. The proof reduces to showing that the cyclic tournament has diameter $2$.

Another approach uses binary residues. Label the vertices by integers modulo $n$ and orient edges according to membership in a suitably chosen difference set. The required property then becomes a statement that every residue is either in the difference set or is a sum of two elements of the difference set. This viewpoint is more algebraic, whereas the circular construction above gives a direct geometric description and a shorter verification.