Kvant Math Problem 847

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m14s
Source on kvant.digital

Problem

A square is divided into $n\times n$ cells. Two players take turns, alternately drawing one side of a cell (it is not allowed to draw the same side twice). Who wins under optimal play if

the player who first forms a closed loop wins;
the player who is forced to form a closed loop first loses.

I. V. Vetrov, A. G. Kogan

Exploration

The game is played on the edge set of the $n\times n$ square grid graph. Each move consists of selecting an unused edge. The only restriction is that a player is not allowed to select an edge that has already been drawn. A cycle is considered to be formed exactly when the chosen edges contain a closed loop.

In both variants, the decisive moment is when a player has no legal move that avoids creating a cycle. In the second rule this situation is explicitly losing; in the first rule, the first player to create a cycle wins, which is equivalent to the previous situation because the cycle appears exactly when the next move is forced to create it.

The key structural question is therefore whether the game can proceed indefinitely without forming a cycle until all edges are exhausted in a controlled way, and how many moves are played before a cycle becomes unavoidable. Small cases suggest that the total number of moves is fixed and equal to the size of a spanning tree of the grid graph, namely $n^2 - 1$, which immediately suggests a parity-based outcome.

The delicate point is to justify that the players are always able to continue playing without creating a cycle until a spanning tree of the grid graph is formed. This requires proving that as long as the chosen edges form a forest that is not yet spanning, there always exists an unused edge connecting different connected components of the chosen forest.

Problem Understanding

This is a Type B problem.

The game is played on the edges of the $n\times n$ grid graph. Two players alternately select unused edges. The key restriction is that selecting edges must avoid creating a cycle until it becomes unavoidable.

The central difficulty is to determine whether play is forced to proceed until a spanning tree is formed and whether the outcome depends only on the parity of the number of vertices $n^2$.

The answer will depend on whether the total number of forced moves is $n^2 - 1$, in which case the first player wins if and only if this number is odd.

Proof Architecture

The first lemma states that as long as the selected edges form a forest that is not spanning, there exists an unused edge connecting two different connected components of the forest.

The second lemma establishes that any maximal legal play produces a spanning tree of the grid graph, hence uses exactly $n^2 - 1$ edges.

The third lemma computes the parity of $n^2 - 1$ and connects it to the first player’s winning condition under normal play.

The hardest step is the first lemma, since it requires relating connectivity in the original grid graph to connectivity in the dynamically built forest.

Solution

Let $G$ be the graph whose vertices are the $n^2$ cells and whose edges are the shared sides of adjacent cells. A position in the game is a set $F$ of edges of $G$ chosen so far. By construction, $F$ is always a forest, since a move that would create a cycle is either forbidden or immediately losing depending on the rule version.

Assume $F$ is a forest and is not spanning, so it has at least two connected components. Let $A$ and $B$ be distinct components of $F$. Since $G$ is connected, there exists a path in $G$ from a vertex in $A$ to a vertex in $B$. Along this path, consider the first edge that leaves $A$. This edge connects a vertex of $A$ to a vertex outside $A$, hence to a different component of $F$, since otherwise that vertex would already belong to $A$. Therefore this edge connects two distinct components of $F$, so adding it does not create a cycle in $F$. Consequently, a legal move always exists as long as $F$ is not spanning.

It follows that play continues until the chosen edges form a spanning tree of $G$. Since $G$ is connected and has $n^2$ vertices, every spanning tree contains exactly $n^2 - 1$ edges, so the game consists of exactly $n^2 - 1$ moves under optimal or forced play.

In the first rule, the first player to create a cycle is the player who has no move that keeps the forest acyclic, which occurs exactly after the last safe move. Hence the winner is determined by the parity of $n^2 - 1$.

If $n$ is even, then $n^2$ is even, so $n^2 - 1$ is odd. The first player makes the final move, so the first player wins. If $n$ is odd, then $n^2$ is odd, so $n^2 - 1$ is even. The second player makes the final move, so the second player wins.

The second rule is equivalent in outcome because the first time a cycle becomes unavoidable corresponds to the same terminal move, so the same parity argument applies.

Therefore the first player wins if and only if $n$ is even, and the second player wins if and only if $n$ is odd. ∎

Verification of Key Steps

The crucial point is the existence of a safe edge while the chosen graph is not spanning. Suppose a forest $F$ has at least two components. Since the original grid graph $G$ is connected, for any two components $A$ and $B$ there exists a path in $G$ connecting them. Along this path, the first edge leaving $A$ must connect $A$ to a vertex not in $A$, and hence to a different component of $F$. This edge is unused and does not close a cycle because its endpoints lie in distinct components of $F$.

The second key step is that every maximal legal position must be a spanning tree. If the final forest were not spanning, then it would have at least two components, contradicting the existence of a safe edge established above.

The third step is that every spanning tree of a connected graph on $n^2$ vertices has exactly $n^2 - 1$ edges, which follows by induction on the number of vertices, removing a leaf vertex at each step.

Alternative Approaches

One alternative viewpoint is to interpret the game as a matroid basis-building process in the graphic matroid of the grid graph. Legal moves correspond to maintaining independence, and maximal plays correspond exactly to bases of the matroid, i.e. spanning trees. The conclusion then follows from the fact that all bases have equal size and the game reduces to a parity argument on that fixed size.