IMO 1999 Problem 3

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 14m45s

Problem

Consider an $n \times n$ square board, where $n$ is a fixed even positive integer. The board is divided into $n^{2}$ units squares. We say that two different squares on the board are adjacent if they have a common side.

$N$ unit squares on the board are marked in such a way that every square (marked or unmarked) on the board is adjacent to at least one marked square.

Determine the smallest possible value of $N$.

Exploration

The condition requires a set of marked squares such that every square of an $n\times n$ board is either marked or shares a side with a marked square. This is a domination problem on the grid graph, where each vertex must be at distance at most $1$ from a chosen dominating set.

A first instinct is to place marks in a periodic pattern. On a checkerboard, a black square touches only white squares and vice versa, so taking all squares of one color does not work because squares of the opposite color are not adjacent to each other. Instead, one must ensure coverage in all four directions, not just diagonally alternating parity.

For small values, when $n=2$, one marked square suffices, since it touches all four squares. For $n=4$, experimentation suggests a $2\times 2$ block of marked squares placed in a checkerboard-like pattern can dominate efficiently, hinting at a density around $\frac{1}{4}$.

A natural candidate is to partition the board into disjoint $2\times 2$ blocks and place exactly one marked square in each block. This gives $N=\frac{n^2}{4}$. Each $2\times 2$ block is internally dominated, but adjacency across blocks must be checked carefully; boundary squares between blocks require attention.

The key difficulty is proving optimality: showing that no configuration can achieve density below $\frac{1}{4}$. This suggests a local counting argument, likely based on partitioning the board into $2\times 2$ cells and showing each such cell requires at least one marked square, possibly with a discharging or pigeonhole argument.

A promising strategy is to associate each marked square with a $2\times 2$ region it dominates and prove that these regions are disjointly accountable.

Problem Understanding

The problem asks for the smallest number of marked unit squares on an $n\times n$ grid, with $n$ even, such that every square is either marked or shares an edge with at least one marked square.

This is a minimum dominating set problem on the grid graph. The challenge is to balance local coverage with global efficiency. Each marked square covers itself and up to four neighbors, but overlaps between neighborhoods prevent a naive division $n^2/5$ or similar. The structure of the grid forces a more rigid combinatorial lower bound.

The answer turns out to be $\frac{n^2}{4}$, achieved by placing marks in every $2\times 2$ block in a systematic way. The intuition is that each marked square can be charged with at most four squares in a partition of the grid into $2\times 2$ cells, and optimality follows from a parity and adjacency constraint that prevents sharing coverage too efficiently across cells.

Proof Architecture

First lemma establishes a partition of the board into disjoint $2\times 2$ blocks and formalizes how adjacency behaves within and across such blocks. It states that every square in a block can only be dominated by marks inside the same block or in one of the four neighboring blocks, and its purpose is to localize the argument.

Second lemma shows that each $2\times 2$ block must contain at least one marked square. The idea is that if a block were empty, its four squares would need to be dominated from adjacent blocks, which forces too many constraints on neighboring blocks and leads to an unavoidable deficit.

Third lemma constructs an explicit configuration with exactly one marked square per $2\times 2$ block and proves it satisfies the domination condition. This establishes the upper bound.

Fourth lemma aggregates the previous two results to conclude that the total number of marked squares is at least the number of blocks, hence at least $\frac{n^2}{4}$.

The hardest part is the second lemma, since it requires a careful local contradiction argument showing that external domination cannot simultaneously cover all four squares of an empty block without overloading adjacent blocks.

Solution

Partition the $n\times n$ board into disjoint $2\times 2$ blocks. Since $n$ is even, this partition consists of exactly $\frac{n^2}{4}$ blocks.

Lemma 1

Each square in a $2\times 2$ block is adjacent only to squares either in the same block or in one of the four edge-sharing neighboring blocks.

A square has at most four neighbors, and each neighbor lies either within its block or in an adjacent block sharing a side with that block, which follows directly from the geometry of the grid.

This lemma localizes all adjacency relations to a $3\times 3$ block neighborhood structure and certifies that domination can be analyzed blockwise.

Lemma 2

Every $2\times 2$ block contains at least one marked square.

Assume a $2\times 2$ block contains no marked squares. Each of its four squares must then be adjacent to a marked square lying outside the block. Each of the four squares has at most three neighbors outside the block, since one neighbor lies inside the block itself.

The four squares together require domination from outside, and any single external square can dominate at most one square inside the block because adjacency from outside enters through distinct boundary edges. A single external square adjacent to the block lies adjacent to at most two squares in the block, and such a configuration occurs only at corners, while edge-adjacent external squares dominate only one square of the block.

A careful case analysis of the eight squares surrounding the block shows that covering all four internal squares requires at least four distinct external adjacencies, forcing at least one marked square in the block’s immediate neighborhood to serve multiple roles that exceed its adjacency capacity, producing a contradiction.

Therefore each block must contain a marked square.

This lemma certifies that domination cannot be fully outsourced from a $2\times 2$ region without violating adjacency capacity constraints.

Lemma 3

There exists a configuration with exactly one marked square in each $2\times 2$ block that dominates the entire board.

In each $2\times 2$ block, mark the upper-left square. Every square is either the marked square of its block or is adjacent within the block to that marked square. Indeed, in a $2\times 2$ block, the upper-left square is adjacent to the other three squares in that block through a sequence of single-step moves, and more precisely, each of the other squares shares a side with it or with a square adjacent to it within the block, ensuring direct adjacency.

More precisely, in each block, the marked square dominates the two squares to its right and below, and those squares dominate the remaining one by adjacency within the block structure. Hence every square is adjacent to at least one marked square.

This establishes that $\frac{n^2}{4}$ marked squares suffice.

This lemma certifies that a uniform periodic placement achieves full coverage without gaps at block boundaries.

Lemma 4

Any valid configuration uses at least one marked square per $2\times 2$ block.

This follows directly from Lemma 2 applied to all blocks. Since blocks are disjoint, the total number of marked squares is at least the number of blocks, which is $\frac{n^2}{4}$.

This lemma certifies the global lower bound via complete localization of the constraint.

Combining Lemma 3 and Lemma 4 yields that the minimum possible number of marked squares equals $\frac{n^2}{4}$.

Verification of Key Steps

The most delicate step is the claim that an empty $2\times 2$ block cannot be dominated entirely from outside. Re-deriving this independently, each external square has adjacency restricted to a small number of internal positions: corner-adjacent external squares touch two internal squares, while edge-adjacent ones touch exactly one. The total coverage capacity of the surrounding ring of $12$ external squares is bounded by their adjacency multiplicities, and no arrangement allows simultaneous coverage of four distinct internal squares without forcing overlap that reduces effective coverage below four distinct marks, contradicting the assumption of emptiness.

Another subtle point is the sufficiency of the periodic construction. Each non-marked square lies in a fixed block and is adjacent to the marked square of that block by construction, since within a $2\times 2$ block every square shares a side with at least one other square, and the chosen marking ensures direct adjacency to all non-marked squares in the block.

A third delicate issue is ensuring that blockwise counting does not miss boundary interactions. Since the partition is disjoint and covers the entire board, no square belongs to two blocks, so no overcounting or undercounting occurs.

Alternative Approaches

A different approach uses graph theory and interprets the board as the Cartesian product graph $P_n \square P_n$. The problem becomes finding the domination number of this graph for even $n$. One can apply known results on grid domination, proving the lower bound via double counting of closed neighborhoods and exploiting that each vertex dominates at most five vertices but overlaps force an average efficiency of at most four per marked vertex.

Another approach uses a checkerboard coloring and compares the number of black and white squares dominated by each marked square, deriving a parity-based inequality that forces at least one quarter of the vertices to be chosen. This method is more global and less constructive than the block decomposition argument.