IMO 1999 SL C5

Origin: BLR | Category: Combinatorics

Problem

Let n be an even positive integer. We say that two dif- ferent cells of an n \times n board are neighboring if they have a common side. Find the minimal number of cells on the n\timesn board that must be marked so that every cell (marked or not marked) has a marked neighboring cell.

Solution

Let n = 2k. Color the cells neigh- boring the edge of the board black. Then color the cells neighboring the black cells white. Then in alterna- tion color the still uncolored cells neighboring the white or black cells on the boundary the opposite color and repeat until all cells are colored. We call the cells colored the same color in each such iteration a “frame.” In the color scheme described, each cell (white or black) neighbors exactly two black cells. The number of black cells is 2k(k + 1), and hence we need to mark at least k(k + 1) cells. On the other hand, going along each black-colored frame, we can alter- nately mark two consecutive cells and then not mark two consecutive cells. Every cell on the black frame will have one marked neighbor. One can ar- range these sequences on two consecutive black frames such that each cell in the white frame in between has exactly one neighbor. Hence, starting from a sequence on the largest frame we obtain a marking that contains exactly half of all the black cells, i.e., k(k + 1) and neighbors every cell. It follows that the desired minimal number of markings is k(k + 1). Remark. For n = 4k −1 and n = 4k +1 one can perform similar markings to obtain minimal numbers 4k2 −1 and (2k + 1)2, respectively.