Olympiad Maths Prep

Library / /13 of 16

Combinatorics Difficulty 6.7 National olympiad Prove it Romania

The unit squares of a n×nn \times n board, n2n \ge 2, are colored either black or white so that any black square has at least three white neighbors (a neighbor is a unit square with a common side). What is the maximum number of black unit squares?

Solution

The answer is n212\frac{n^2-1}{2} if nn is odd and n242\frac{n^2-4}{2} if nn is even.

Notice that:

* the unit squares from the corners are white (because they only have two neighbors, not three);
* the other squares from the border of the board have only three neighbors, so there can't be two consecutive black squares on the border;
* any 2×22 \times 2 square contains at most two black squares (if not, a black square would already have two black neighbors, so it would have at most two white neighbors).

If nn is odd, color the board like a chessboard with white corners. This coloring satisfies the requirements of the problem and it has n212\frac{n^2-1}{2} black squares, so the maximum number of black squares is at least n212\frac{n^2-1}{2}.

On the other hand, split the board in 4 parts: one upper-left (n1)×(n1)(n-1) \times (n-1) square, a unit square in the right bottom corner, a (n1)×1(n-1) \times 1 rectangle on the right side and a 1×(n1)1 \times (n-1) rectangle on the bottom side. Tiling the (n1)×(n1)(n-1) \times (n-1) square with 2×22 \times 2 squares and the two rectangles with 2-square dominoes, according with the remarks made at the beginning, one can have at most
(n1)22+n12+n12+0=n212 \frac{(n-1)^2}{2} + \frac{n-1}{2} + \frac{n-1}{2} + 0 = \frac{n^2-1}{2}
black squares.

If nn is even, again consider a chessboard-like coloring. This makes two white corners and two black corners; recolor the black corners as white. The configuration we have now satisfies the requirements of the problem and it has n242\frac{n^2-4}{2} black squares, so the maximum number of black squares is at least n242\frac{n^2-4}{2}.

Split the board in 9 parts: one (n2)×(n2)(n-2) \times (n-2) square in the middle, four unit squares in the corners and four (n2)×1(n-2) \times 1 or 1×(n2)1 \times (n-2) rectangles on the borders. Tiling the (n2)×(n2)(n-2) \times (n-2) square with 2×22 \times 2 squares and the rectangles with 2-square dominoes, the remarks made at the beginning lead to a maximum of
(n2)22+4n22+40=n242 \frac{(n-2)^2}{2} + 4 \cdot \frac{n-2}{2} + 4 \cdot 0 = \frac{n^2-4}{2}
black squares. Hence, if nn is even, the maximum number of black squares is n242\frac{n^2-4}{2}.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.