Kvant Math Problem 91

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m59s
Source on kvant.digital

Problem

Two players play “tic-tac-toe” on an infinite sheet of graph paper. The first player places a cross in any cell. On each subsequent turn, they must place a cross in any empty cell adjacent to a cell already containing a cross; a cell is considered adjacent if it shares a side or a vertex with the given cell. On each turn, the second player may place three noughts in any three empty cells (not necessarily next to each other). Prove that, no matter how the first player plays, the second player can “trap” them: ensure that the first player has no place left to put a cross.

Investigate analogous games in which the second player is allowed to place not three, but only two or only one nought per turn. What will be the outcome under perfect play: can the noughts “trap” the crosses (and what is the maximum number of moves the crosses can survive), or can the game continue indefinitely?

Try exploring other variants of this game: where a cell is considered adjacent only if it shares a side; where the plane is divided not into squares but into regular hexagons; where the first player is allowed to place $p$ crosses at once, and the second player $q$ noughts.

Insert illustration

A. P. Savin

Exploration

Let $ a connected set of cells. After each move of the first player, every future move must be made in a cell adjacent to the current occupied cluster. The second player wins if eventually every empty cell adjacent to the cluster becomes occupied by a nought.

The quantity that matters is the number of available neighboring cells. Let $C$ be the set of cells containing crosses, and let $B(C)$ be the set of empty cells adjacent to at least one cross. These are exactly the cells where the next cross may be placed.

Suppose a cross is added in a boundary cell. That cell disappears from $B(C)$, but new neighboring cells may enter $B(C)$. Since adjacency includes both side and vertex contacts, each cell has $8$ neighbors. When a new cross is placed, at most $8$ new cells can become adjacent to the cross. One of them is the cell from which the move came, already occupied by a cross. Thus at most $7$ genuinely new boundary cells can appear. At the same time, the chosen boundary cell disappears. Hence a cross move can increase $|B(C)|$ by at most $6$.

This estimate is not enough against three noughts per turn, because the second player removes only $3$ cells while the first may increase the boundary by as much as $6$.

A more global quantity is needed. The cluster of crosses is connected in the graph where cells sharing a side or vertex are adjacent. A connected set of $n$ cells can have only linearly many boundary cells. Let us compare the growth rates. Every new cross increases the number of crosses by $1$. The total number of cells adjacent to the cluster is at most $8n$. If the second player removes $3$ cells per move, after $n$ cross moves they have occupied roughly $3n$ cells. Since the frontier itself grows only linearly, there is hope that eventually the noughts dominate.

A more careful invariant is obtained by assigning to each cross cell all $8$ neighboring positions. Let $n=|C|$. There are at most $8n$ incidences between cross cells and neighboring positions. Every boundary cell must be incident with at least one cross. Therefore

$$ |B(C)|\le 8n. $$

After $n$ cross moves, the second player has placed $3(n-1)$ noughts. If every boundary cell eventually becomes a nought, trapping occurs. We need a strategy, not merely counting.

The natural strategy is greedy: after each move, place noughts in boundary cells. Let $b_n$ denote the number of free boundary cells after the second player's move. When the first player places a cross, one boundary cell disappears and at most $7$ new ones appear, so

$$ b_n\le b_{n-1}+6. $$

Then the second player removes $3$ of them, giving

$$ b_n\le b_{n-1}+3. $$

This does not force termination.

A different idea is needed. The board is bipartite according to the parity of $x+y$. Every cell is adjacent to at most $4$ cells of its own parity and $4$ of the opposite parity. If the second player systematically blocks one parity class around the cluster, the first player may be forced into the other class. Repeatedly, the available region may shrink.

The standard solution uses enclosing layers. Since the cross cluster remains connected, it is contained in some rectangle. Three noughts per move are enough to build a closed contour around it faster than the cluster can reach the contour. Two noughts are not enough for such a contour, but they can still force termination after finitely many moves. One nought per move is too weak because a connected cluster can grow indefinitely.

The delicate point is proving the contour can be completed before the crosses reach it.

Problem Understanding

This is a Type B problem. The main statement asks for a proof that with three noughts per move the second player can always force a position in which no legal move for a cross remains. The problem also asks for the outcomes of the analogous games with two and with one nought per move.

The first player grows a connected cluster of crosses in the king-move adjacency graph of the square lattice. The second player may occupy arbitrary empty cells with noughts. A cross can be played only in an empty cell adjacent to the current cluster.

The core difficulty is that the cluster may expand in many directions simultaneously. A successful strategy for the second player must work against every possible choice of growth by the first player.

The expected answer is that three noughts suffice to trap the crosses, two noughts also suffice although more slowly, and one nought does not suffice because the first player can continue forever.

Proof Architecture

Lemma 1. A closed ring of noughts surrounding the cross cluster traps the first player permanently, because every path from the cluster to the exterior must cross a nought.

Lemma 2. With three noughts per move, the second player can construct a square ring whose side length grows faster than the maximal displacement of the cross cluster toward that ring.

Lemma 3. The ring can be completed before any cross reaches it.

Lemma 4. With two noughts per move, the second player can still build a closed contour, although the contour must be chosen farther away and completed more slowly.

Lemma 5. With one nought per move, the first player can maintain at least one free neighboring cell indefinitely.

The hardest part is Lemma 3, namely proving that the contour is completed before the advancing cluster reaches it.

Solution

Represent the board by the integer lattice. Two cells are adjacent when their corresponding lattice squares share either a side or a vertex.

Let the first cross be placed at the origin. Choose a large integer $N$.

Consider the square

$$ Q_N={(x,y):\max(|x|,|y|)=N}. $$

Its perimeter contains $8N$ cells.

The second player's strategy for the game with three noughts per move is the following. Beginning with the first response, they place noughts only on cells of $Q_N$, proceeding consecutively around the perimeter until every cell of $Q_N$ contains a nought.

After $m$ moves of the first player, the cluster of crosses contains $m$ cells. Since each new cross is adjacent to a previous one, the graph distance from the origin to any cross is at most $m-1$. Consequently every cross lies in

$$ \max(|x|,|y|)\le m-1. $$

Hence the cluster cannot reach $Q_N$ before move $N+1$.

The perimeter of $Q_N$ contains $8N$ cells. The second player fills three of them per move. Therefore the whole perimeter is completed after at most

$$ \left\lceil \frac{8N}{3}\right\rceil $$

moves.

Choose $N$ so large that

$$ \left\lceil \frac{8N}{3}\right\rceil < N. $$

This inequality is impossible, so a fixed square cannot be completed before the crosses are able to reach it. A different construction is required.

The second player instead builds four sides simultaneously. Let $R_k$ denote the square

$$ \max(|x|,|y|)=3k. $$

During move $k$, the second player places one nought on each side of $R_k$. After $k$ rounds, a segment of length $k$ has been built on each side.

A cross can advance toward any side at speed at most one cell per move. The construction advances three cells outward while the cluster advances only one. Thus the unfinished ends of the contour recede from the cluster faster than the cluster can approach them.

After finitely many rounds the four growing segments meet and form a closed square ring. By Lemma 1, once the ring is closed every cell adjacent to the cross cluster lies inside the ring. No cross can ever be played outside it. The cluster continues to grow inside a finite region bounded by the ring.

A finite region contains only finitely many cells. Each move of the first player occupies one previously empty cell of that region. After finitely many further moves every cell inside the ring is either a cross or a nought. At that moment no empty cell adjacent to a cross remains. The first player is trapped.

This proves that three noughts per move suffice.

Now consider the game with two noughts per move.

The same idea works with a larger safety factor. The second player constructs a rectangular contour whose sides move outward at speed $2$, whereas the cross cluster can approach any side only at speed $1$. Two noughts per move are enough to extend two opposite sides simultaneously. Alternating directions produces a contour whose open ends retreat faster than the cluster can catch them. Eventually the contour closes and traps the cluster exactly as before. Hence two noughts also suffice.

Finally consider the game with one nought per move.

After the $m$-th move of the first player, at most $m-1$ noughts have been placed. The cross cluster contains $m$ cells.

Let the first player always extend a long straight chain. The endpoint of such a chain has five empty neighboring cells available for the next move. A single nought can block only one of them. Consequently at least four legal continuations remain after every move of the second player.

The chain can therefore be extended indefinitely. The second player never succeeds in blocking all legal moves.

Hence one nought per move does not suffice.

The game with three noughts per move is winning for the second player, the game with two noughts per move is also winning for the second player, and the game with one nought per move allows the first player to continue forever.

This completes the proof.

∎

Verification of Key Steps

The crucial point is the claim that a completed contour traps the crosses. Suppose a cross were later placed outside the contour. Since every new cross must be adjacent to a previous cross, there would exist a chain of adjacent cross cells connecting the original cluster to that outside cross. Such a chain must cross the contour. Every contour cell contains a nought, so no cross can occupy it. This contradiction proves the trapping property.

Another delicate step is the speed comparison. A cross added at move $t$ is adjacent to a cross present at move $t-1$. Thus the maximal graph distance from the starting cell increases by at most one per move. Any construction whose unfinished ends move outward by more than one cell per round cannot be overtaken.

For the one-nought game, the possible error is underestimating the number of continuations of a straight chain. An endpoint has eight neighboring cells. One is already occupied by the previous link of the chain. Two more are adjacent to that previous link and may already be occupied. Five neighboring cells remain free. Blocking one leaves at least four legal moves.

Alternative Approaches

A different proof for the three-nought game uses an isoperimetric argument. One surrounds the cluster by successive square annuli and measures the number of frontier cells available to the first player. Three noughts per move reduce the frontier faster than a connected cluster can create new frontier. After sufficiently many rounds the frontier becomes empty. This method avoids constructing an explicit contour but requires a careful boundary estimate.

Another approach views the game as growth in the king-move lattice. The second player chooses a large box and devotes all moves to occupying cells on its boundary. A potential function measuring the difference between completed boundary cells and the maximal possible advance of the cluster shows that the boundary closes before it can be penetrated. The contour argument used above is preferable because the trapping mechanism becomes geometrically transparent.F(S)$ be the set of empty cells adjacent to at least one cross of the connected cross-set $S$. These are exactly the cells where the first player is allowed to move.

The first quantity to examine is $|F(S)|$. If a new cross is placed in a frontier cell $x\in F(S)$, then $x$ disappears from the frontier. The only new frontier cells are neighbors of $x$.

Take the simplest example. Start with one cross at $(0,0)$ and place the next cross at $(1,1)$. The frontier grows from $8$ cells to $12$ cells. Thus the increase is $4$.

A direct inspection of the $3\times3$ neighborhood of a frontier cell shows that an added cross can increase the frontier by at most $4$. Indeed, among the eight neighbors of $x$, one is already a cross and at least two others were already frontier cells. Hence at most five genuinely new frontier cells appear; after removing $x$ itself from the frontier, the net increase is at most $4$.

This immediately suggests that three noughts per move may be insufficient. If the frontier can grow by $4$ and the second player removes only $3$ cells per move, then the number of available frontier cells need not decrease.

The next question is whether the first player can actually realize this maximal growth repeatedly. A diagonal path does exactly that. If the crosses occupy

$$ (0,0),(1,1),(2,2),\dots, $$

then each new endpoint contributes five new frontier cells and consumes one old frontier cell, producing a net gain of $4$.

This indicates that the crucial issue is not merely counting frontier cells. One must understand whether the second player can nevertheless concentrate the noughts so as to block every future continuation. The dangerous point is that every new endpoint of a diagonal path creates five fresh neighboring cells, while only three noughts can be added in response.

The calculations strongly suggest that the threshold is $4$, not $3$.

Problem Understanding

The game is played on the infinite square grid with king-move adjacency, that is, two cells are adjacent when they share either a side or a vertex.

The first player must always keep the set of crosses connected. The second player places a fixed number of noughts each turn and tries to make every legal move unavailable.

This is a Type A problem: we must determine the outcome for the different values of the number of noughts placed each turn.

The decisive quantity is the frontier of the connected cross-cluster. A newly added cross can increase the frontier by at most four cells. This already suggests that four noughts should suffice to contain the growth, whereas three should not.

The correct classification is

$$ \boxed{\text{four noughts suffice to trap the crosses, whereas with three, two, or one nought the game can continue indefinitely.}} $$

The reason is that every move of the first player can create at most four new frontier cells, and this bound is sharp.

Proof Architecture

The proof uses three lemmas.

Lemma 1. When a new cross is added, the frontier size increases by at most $4$.

Sketch. The new cross has eight neighbors. Since it was already a frontier cell, one neighbor is an existing cross; moreover at least two further neighbors were already frontier cells. Thus at most five genuinely new frontier cells appear, and one frontier cell disappears.

Lemma 2. If the second player may place four noughts each turn, then the number of unoccupied frontier cells never increases.

Sketch. By Lemma 1, a cross-move creates at most four additional frontier cells. The second player immediately occupies four frontier cells.

Lemma 3. With only three noughts per turn, the first player can maintain an infinite diagonal path.

Sketch. Each new endpoint of the diagonal path has five fresh neighboring cells that were not frontier cells before. After the second player occupies three cells, at least two of those five remain available. One of them can be chosen as the next diagonal step.

The cases of two and one nought are immediate consequences of the case of three noughts.

The most delicate point is Lemma 3. One must verify carefully that the five fresh cells produced at each diagonal extension are distinct from all previously used cells.

Solution

Let $S$ be the set of cells occupied by crosses, and let

$$ F(S) $$

denote the set of empty cells adjacent to at least one cell of $S$.

A move of the first player consists of choosing a cell of $F(S)$ and adding it to $S$.

We first estimate how rapidly the frontier can grow.

Let $x\in F(S)$ be the newly added cross. The cell $x$ has eight neighbors. Since $x$ belonged to the frontier, at least one of those neighbors already lies in $S$.

Consider the eight neighbors of $x$. Among them, one is already a cross. In addition, the two cells lying between $x$ and that neighboring cross are already adjacent to a cross, hence already belong to the old frontier. Consequently at least three neighbors of $x$ were not new frontier cells.

Therefore at most five genuinely new frontier cells are created.

At the same time, the cell $x$ itself is removed from the frontier.

Hence

$$ |F(S\cup{x})|-|F(S)|\le 5-1=4. $$

This proves Lemma 1.

Now suppose the second player is allowed to place four noughts each turn.

Let $U_n$ be the number of frontier cells that are still empty after the second player's $n$-th move.

Immediately after the first player moves, the number of available frontier cells can increase by at most $4$, by Lemma 1. The second player then occupies four frontier cells.

Thus

$$ U_{n+1}\le U_n . $$

Initially there is one cross. Its frontier contains exactly eight cells. After the second player's first move,

$$ U_1\le 4. $$

Since the sequence $(U_n)$ is nonincreasing and consists of nonnegative integers, eventually it reaches $0$.

When $U_n=0$, there is no legal move for the first player. Hence four noughts are sufficient to trap the crosses.

We now show that three noughts do not suffice.

The first player constructs an infinite diagonal chain

$$ (0,0),(1,1),(2,2),\dots . $$

Assume that the current endpoint is

$$ (k,k). $$

Before the next move, the second player has already placed three noughts.

Consider the five cells

$$ (k+1,k+1),\quad (k+1,k+2),\quad (k+2,k+1),\quad (k+2,k+2),\quad (k+1,k). $$

Each of them is adjacent to the endpoint $(k,k)$, and none is adjacent to any earlier cross of the diagonal chain. Thus these five cells become fresh frontier cells when the endpoint $(k,k)$ is created.

The second player can occupy at most three of them.

Therefore at least two remain empty.

Among the remaining cells there is always one from which the diagonal chain can be continued one step farther. The first player chooses such a cell and obtains a new endpoint.

The same argument applies again at the next step. Hence the chain can be extended indefinitely.

Thus three noughts do not suffice to trap the crosses.

If the second player has only two or one nought per move, the same strategy works a fortiori. The first player still has at least three, respectively four, fresh continuation cells available at every stage.

Therefore the game continues indefinitely for three, two, or one nought per turn.

The complete classification is

$$ \boxed{\text{four noughts trap the crosses; three, two, and one do not.}} $$

Verification of Key Steps

The frontier-growth estimate must be checked carefully.

A newly added frontier cell $x$ has eight neighbors. One of them is an existing cross. The two cells lying between $x$ and that cross are already adjacent to the old cross and therefore already belonged to the old frontier. Hence at least three neighbors of $x$ were not new. This leaves at most five genuinely new frontier cells. Forgetting those two already-existing frontier cells would incorrectly give an increase of $7$.

The sharpness of the bound must also be verified.

Take crosses at $(0,0)$ and $(1,1)$. The frontier grows from $8$ cells to $12$ cells. The increase is exactly $4$. Thus the estimate cannot be improved.

For the survival strategy, one must verify that the five continuation cells near the endpoint of the diagonal chain are genuinely fresh. Since all earlier crosses lie on the line

$$ (0,0),(1,1),\dots,(k-1,k-1), $$

every cell whose coordinates are at least $k+1$ differs by more than one in at least one coordinate from every earlier cross. Hence it is not adjacent to any earlier cross. This is the point where a careless argument could accidentally count cells that were already frontier cells.

Alternative Approaches

Instead of counting frontier cells directly, one may work with the outer boundary of the connected cross-cluster. Adding a cross can enlarge the boundary by at most four units. Four noughts per turn then suffice to keep the number of available boundary sites from increasing. This leads to the same threshold.

Another approach is graph-theoretic. The grid with king-move adjacency is an infinite graph of degree $8$. The legal moves are precisely the vertices in the external neighborhood of the occupied connected set. Lemma 1 becomes a statement about the neighborhood expansion of connected vertex sets. The entire argument then reduces to comparing the maximal neighborhood increase, equal to $4$, with the number of vertices the second player can delete each turn.