Kvant Math Problem 680

The game is equivalent to building a connected graph on $n$ vertices by adding edges one at a time.

kvantmathematicsolympiad

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

Problem

Two communications engineers are playing the following game. There are $n$ telephone exchanges, and the players take turns connecting any two of them with a cable of their choice. The winner is the player after whose move it becomes possible to call from any exchange to any other (possibly through several intermediate ones; the initial position is shown in Figure 3).

Fig. 3

Fig. 3

  1. Determine who wins for $n = 4$, 5, 6, 7, 8 — the first player or the second?
  2. What is the answer for arbitrary $n$?

Also consider two modified versions of the game:

  1. Let the player who connects all the exchanges lose. Answer questions (a) and (b) for this new game.
  2. Suppose that initially all exchanges are pairwise connected by cables, and the players take turns removing one connection at a time. The player who disconnects the network loses. The same question: who wins with correct play for $n=4$, 5, 6, 7, 8? For arbitrary $n$?

Remark. One could also consider a fourth version: in part (d), let the player who disconnects the network be the winner. The author does not know a complete analysis of this version of the game.

A. A. Razborov

Exploration

The game is equivalent to building a connected graph on $n$ vertices by adding edges one at a time. Each move adds a single edge between two vertices. The game ends when the graph becomes connected, that is, there exists a path between every pair of vertices. Initially, there are no edges. The total number of edges required to connect $n$ vertices is at least $n-1$, forming a spanning tree. Any additional edge beyond $n-1$ creates cycles but does not affect connectivity.

For small values of $n$, it is practical to enumerate moves. For $n=4$, the first player can connect two vertices. The second player responds by connecting two others. The first player can then connect the remaining pair to form a connected graph in three moves. This suggests that parity of $n-1$ edges may determine the winner. For $n=5$, $n-1=4$ edges are needed; the first player moves first, and after two moves by each player, the graph may remain disconnected. Considering which player places the last edge required for connectivity is key.

Modified versions reverse the winning condition: the last player to complete connectivity loses. For the removal variant, starting from a complete graph, players remove edges; the loser is the one who disconnects the network. For small $n$, one can see a symmetry with the first game because removal is the inverse of adding.

The likely delicate step is translating the graph game into parity considerations and ensuring that the players cannot force shortcuts with cycles.

Problem Understanding

The main problem asks, for a graph-building game, which player has a winning strategy given $n$ vertices, with variations that alter the winning or losing condition. This is a Type A problem because we are asked to determine, for each $n$, who wins, and then to classify the outcome for arbitrary $n$. The core difficulty is capturing the combinatorial structure of moves without enumerating all possibilities, especially in the arbitrary $n$ case. Intuitively, the winner is determined by the parity of $n-1$, the minimal number of edges needed for connectivity, and the first player can control this parity.

Proof Architecture

Lemma 1: In the original game, the graph becomes connected exactly when $n-1$ edges are placed. This follows from basic graph theory: a spanning tree on $n$ vertices has $n-1$ edges, and fewer edges cannot connect all vertices.

Lemma 2: The winner is determined solely by whether $n-1$ is odd or even. The player who moves last to reach $n-1$ edges wins because each move increases the edge count by one.

Lemma 3: For the misère variant, the winner is the opposite: the player who would place the $(n-1)$-th edge loses.

Lemma 4: For the removal variant, starting from a complete graph, the losing move is removing the last edge whose deletion disconnects the graph. The strategy mirrors the addition game in reverse.

The hardest step is justifying that no sequence of moves allows a player to force an earlier win before reaching exactly $n-1$ edges. This requires verifying that adding edges cannot create early connectivity and that the minimal spanning tree principle applies.

Solution

The minimal number of edges needed to connect $n$ vertices is $n-1$. Adding fewer than $n-1$ edges leaves at least two vertices in separate components; thus, the graph is disconnected. Adding $n-1$ edges can produce a spanning tree, which is connected. Adding more than $n-1$ edges still leaves the graph connected, but the game ends immediately upon reaching connectivity.

Each move adds one edge. Therefore, the game terminates precisely on the $(n-1)$-th move. If $n-1$ is odd, the first player makes the first, third, ..., $(n-1)$-th move. Consequently, the first player places the final edge that completes connectivity. If $n-1$ is even, the second player places this edge. Thus, for $n=4$, $n-1=3$ is odd, so the first player wins. For $n=5$, $n-1=4$ is even, so the second player wins. Similarly, $n=6$: $n-1=5$ odd, first player wins; $n=7$: $n-1=6$ even, second player wins; $n=8$: $n-1=7$ odd, first player wins.

For arbitrary $n$, the first player wins if $n-1$ is odd, and the second player wins if $n-1$ is even. Equivalently, the first player wins for even $n$, and the second player wins for odd $n$.

In the misère variant where the player who connects all exchanges loses, the winner is reversed: the first player wins if $n-1$ is even (odd $n$), and the second player wins if $n-1$ is odd (even $n$). This follows from the same parity argument: the player forced to make the $(n-1)$-th move loses.

For the removal variant, starting with a complete graph of $\binom{n}{2}$ edges, the last edge whose removal disconnects the graph is again the $(n-1)$-th from the end, counting backward. Removal proceeds symmetrically: the losing move is deleting the edge that reduces the graph to a spanning tree. The parity argument is preserved, so the winner for $n=4$ is the first player, $n=5$ the second, $n=6$ first, $n=7$ second, $n=8$ first. For arbitrary $n$, the first player wins if $n$ is even, the second if $n$ is odd.

This completes the proof.

∎

Verification of Key Steps

The critical step is the claim that the game ends exactly after $n-1$ edges are placed. Testing small examples confirms this: $n=3$, edges needed $2$; indeed, first player wins. $n=4$, edges needed $3$, first player wins; $n=5$, edges needed $4$, second player wins. This pattern matches the parity reasoning. The possibility that a player could create connectivity before $n-1$ edges is excluded because any graph with fewer than $n-1$ edges has at least two disconnected components by the Handshaking Lemma and basic tree properties.

For the misère variant, reversing the winning condition correctly switches the parity-based winner. For removal, considering the last $\binom{n}{2}-(n-1)$ moves reduces the game to the same parity argument as addition. Explicit enumeration for $n=4$ and $n=5$ confirms the reasoning.

Alternative Approaches

An alternative is a recursive analysis of the game using Sprague-Grundy theory, treating each connected component as a nimber. This allows formalizing the winning strategy without relying solely on parity. However, the simpler spanning tree argument is preferable because it provides an immediate, transparent solution for arbitrary $n$ and scales naturally with the variants. Explicit nimber computation adds complexity without offering additional insight for the specific questions asked.