IMO 1999 · Problem 3

Consider an \(n \times n\) square board, where \(n\) is a fixed even positive integer. The board is divided into \(n^2\) unit 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\).

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{N_{\min}=\frac{n(n+2)}4}. \]

Solution

Write \(n=2k\). We will construct a set \(T\) of \(k(k+1)\) squares such that every square has exactly one neighbour in \(T\). This property will also give the required lower bound.

Label the squares \((i,j)\), where \(1\le i,j\le n\), and colour a square black when \(i+j\) is even and white otherwise.

Define a set \(A\) of black squares by the following rule:

  • On each diagonal \(i+j\equiv n\pmod 4\) with \(i+j\le n\), select the squares whose two coordinates are odd.
  • On each diagonal \(i+j\equiv n\pmod 4\) with \(i+j>n\), select the squares whose two coordinates are even.

We claim that every white square has exactly one neighbour in \(A\).

Indeed, let \((i,j)\) be white and put \(t=i+j\), which is odd. Exactly one of \(t-1,t+1\) is congruent to \(n\pmod4\); call it \(s\). Only neighbours on the diagonal with coordinate sum \(s\) can belong to \(A\).

There are two potential neighbours on this diagonal. If both lie on the board, one has two odd coordinates and the other has two even coordinates. Thus exactly one belongs to \(A\), according as \(s\le n\) or \(s>n\).

It remains to check the boundary:

  • If \(s=t-1\) and a potential neighbour lies outside the board, then \(i=1\) or \(j=1\). Consequently \(s\le n\), and the remaining neighbour has two odd coordinates, so it belongs to \(A\).
  • If \(s=t+1\) and a potential neighbour lies outside the board, then \(i=n\) or \(j=n\). Consequently \(s>n\), and the remaining neighbour has two even coordinates, so it belongs to \(A\).

Both potential neighbours cannot lie outside: this would require the square to be \((1,1)\) or \((n,n)\), both of which are black. The claim follows.

Now reflect \(A\) across the vertical midline of the board, obtaining \[ A'=\{(i,n+1-j):(i,j)\in A\}. \] Since \(n\) is even, this reflection interchanges black and white squares and preserves adjacency. Hence \(A'\) consists of white squares, and every black square has exactly one neighbour in \(A'\).

Therefore \[ T=A\cup A' \] has the desired property: every square has exactly one neighbour in \(T\). In particular, marking precisely \(T\) satisfies the condition, including for the marked squares themselves.

We next count \(T\). For an even diagonal sum \(s\le n\), there are \(s/2\) squares with two odd coordinates. For an even sum \(s>n\), there are \(n-s/2+1\) squares with two even coordinates. Thus the diagonals \[ i+j=n,\ n-4,\ n-8,\ldots \] contribute respectively \[ k,\ k-2,\ k-4,\ldots \] squares to \(A\), while the diagonals \[ i+j=n+4,\ n+8,\ n+12,\ldots \] contribute \[ k-1,\ k-3,\ k-5,\ldots. \] Each list stops before its terms become nonpositive. Together their terms are precisely \(1,2,\ldots,k\). Hence \[ |A|=\frac{k(k+1)}2, \qquad |T|=2|A|=k(k+1). \]

Finally, consider any valid marking with \(N\) marked squares. Count pairs \((t,m)\) in which \(t\in T\) and \(m\) is a marked square adjacent to \(t\).

Every \(t\in T\) must have a marked neighbour, so there are at least \(|T|\) such pairs. On the other hand, every marked square has exactly one neighbour in \(T\), so there are exactly \(N\) pairs. Consequently \[ N\ge |T|=k(k+1)=\frac{n(n+2)}4. \] The construction attains this bound, completing the proof.

The solution was checked against Evan Chen's published IMO solution notes.