Verified: yes
Verdicts: PASS + PASS
Solve time: 21m45s
Source on kvant.digital

Problem

On the board, a circle is drawn with $2n$ points marked on it, dividing it into $2n$ equal arcs. Petya and Vasya play the following game. Petya chooses a natural number $d\le n$ and announces it to Vasya. After that, for Vasya to win, he must color all the marked points using $n$ colors, exactly two points per color, so that for each pair of points with the same color, there are exactly $(d-1)$ marked points on one of the arcs between them. Find all $n$ for which Petya can prevent Vasya from winning.

M. Sagafian (Iran)

Caucasian Mathematical Olympiad (X)

Exploration

Label the marked points by the elements of $\mathbb Z_{2n}$ in cyclic order. If two points have exactly $d-1$ marked points on one of the arcs between them, then travelling around that arc uses $d$ edges, so the endpoints differ by $\pm d$ modulo $2n$. Thus the admissible pairs are precisely the edges of the graph

$$G_d=\bigl(\mathbb Z_{2n},{{x,x+d}:x\in\mathbb Z_{2n}}\bigr).$$

Vasya wins precisely when this graph has a perfect matching. The problem becomes a question about the cycle decomposition of $G_d$.

Small cases suggest that the answer depends on the parity of the cycle lengths. For instance, when $n=4$ and $d=2$, the graph consists of two $4$-cycles and a perfect matching exists. When $n=4$ and $d=1$, the graph is an $8$-cycle and again a perfect matching exists. The obstruction appears when some cycle has odd length.

Problem Understanding

For a fixed $d$, every vertex of $G_d$ has degree $2$, except when $d=n$, in which case each vertex has degree $1$. Hence $G_d$ is a disjoint union of cycles, with the special case $d=n$ giving a disjoint union of edges.

A cycle admits a perfect matching if and only if its length is even. Consequently, Vasya can win for a given $d$ exactly when every cycle of $G_d$ has even length.

Petya succeeds if he can choose some $d\le n$ for which at least one cycle of $G_d$ has odd length.

Proof Architecture

The first step is to determine the cycle lengths in $G_d$.

The second step is to characterize when all these lengths are even.

The final step is to determine for which $n$ Petya can choose a value of $d$ producing an odd cycle.

Solution

Fix $d\le n$ and put

$$g=\gcd(2n,d).$$

Starting from a vertex $x$, repeated addition of $d$ modulo $2n$ produces

$$x,\ x+d,\ x+2d,\ \dots.$$

The length of the resulting cycle equals the smallest positive integer $m$ such that

$$md\equiv0\pmod{2n}.$$

Since $g=\gcd(2n,d)$, this minimal value is

$$m=\frac{2n}{g}.$$

There are exactly $g$ cycles, each of length $\frac{2n}{g}$.

When $d=n$, the graph consists of $n$ disjoint edges, because then $g=n$ and the above formula gives cycle length $2$. Hence $d=n$ never creates an obstruction.

A cycle of length $\frac{2n}{g}$ possesses a perfect matching exactly when $\frac{2n}{g}$ is even. Since all cycles have the same length, Vasya wins for this value of $d$ if and only if

$$\frac{2n}{g}\ \text{is even},$$

or equivalently,

$$g\mid n.$$

Indeed, if $g\mid n$, then

$$\frac{2n}{g}=2\cdot\frac{n}{g}$$

is even, and each cycle can be matched by taking alternating edges around the cycle.

If $g\nmid n$, then $\frac{2n}{g}$ is odd, every component is an odd cycle, and no perfect matching exists.

Thus Petya needs a number $d\le n$ such that

$$g=\gcd(2n,d)$$

does not divide $n$.

Write

$$n=2^k m,$$

where $m$ is odd.

Suppose first that $m=1$, so $n=2^k$ is a power of two. Every divisor of $2n=2^{k+1}$ is also a power of two, and every number $d\le n$ satisfies

$$g=\gcd(2n,d)\le d\le n.$$

Hence $g$ is a divisor of $n$, and therefore

$$\frac{2n}{g}$$

is always even. Every component of every graph $G_d$ has even length, so Vasya can always choose perfect matchings inside the components. Petya has no winning choice.

Now assume that $m>1$, so $n$ is not a power of two. Let

$$d=2^k.$$

Since

$$2n=2^{k+1}m,$$

we obtain

$$g=\gcd(2^{k+1}m,2^k)=2^k.$$

Because $m>1$ is odd,

$$\frac{2n}{g}=2m$$

is even. This choice does not help Petya, so another value is needed.

Take

$$d=2^{k+1}.$$

Since $m>1$, we have

$$2^{k+1}\le2^km=n,$$

and therefore this value is allowed. Now

$$g=\gcd(2^{k+1}m,2^{k+1})=2^{k+1}.$$

The cycle length becomes

$$\frac{2n}{g} =\frac{2^{k+1}m}{2^{k+1}} =m,$$

which is odd.

Hence every component of $G_d$ is an odd cycle, and no perfect matching exists. Vasya cannot color the points as required. Petya wins.

Accordingly, Petya can prevent Vasya from winning precisely when $n$ is not a power of two.

$$\boxed{\text{Petya can prevent Vasya from winning if and only if }n\text{ is not a power of }2.}$$

Verification of Key Steps

Take $n=4$. For $d=2$, we have

$$g=\gcd(8,2)=2,$$

so the graph consists of two cycles of length

$$\frac{8}{2}=4.$$

Each $4$-cycle has a perfect matching, hence Vasya wins. The same happens for every admissible $d$, confirming that Petya cannot force a loss.

Take $n=6=2\cdot3$. Choosing

$$d=4=2^{1+1},$$

gives

$$g=\gcd(12,4)=4,$$

and therefore the cycle length is

$$\frac{12}{4}=3.$$

The graph is a disjoint union of four triangles. Since a triangle has no perfect matching, Vasya loses. Thus Petya wins for $n=6$.

Take $n=10=2\cdot5$. Choosing

$$d=4$$

yields

$$g=\gcd(20,4)=4,$$

and the graph decomposes into four $5$-cycles. Again no perfect matching exists.

Alternative Approaches

The graph $G_d$ is the Cayley graph of the cyclic group $\mathbb Z_{2n}$ with generator set ${\pm d}$. Its connected components are cycles of length

$$\frac{2n}{\gcd(2n,d)}.$$

The existence of a perfect matching is equivalent to the evenness of these cycle lengths. Choosing

$$d=2^{v_2(n)+1}$$

when $n$ has an odd factor produces odd cycles and blocks any matching, whereas if $n$ is a power of two, every possible component length is even. This yields the same classification:

$$\boxed{n\neq2^k.}$$