Browse · MathNet
Print67th NMO Selection Tests for JBMO
Romania counting and probability
Problem
The unit squares of a board, , 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 if is odd and if 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 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 is odd, color the board like a chessboard with white corners. This coloring satisfies the requirements of the problem and it has black squares, so the maximum number of black squares is at least .
On the other hand, split the board in 4 parts: one upper-left square, a unit square in the right bottom corner, a rectangle on the right side and a rectangle on the bottom side. Tiling the square with squares and the two rectangles with 2-square dominoes, according with the remarks made at the beginning, one can have at most black squares.
If 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 black squares, so the maximum number of black squares is at least .
Split the board in 9 parts: one square in the middle, four unit squares in the corners and four or rectangles on the borders. Tiling the square with squares and the rectangles with 2-square dominoes, the remarks made at the beginning lead to a maximum of black squares. Hence, if is even, the maximum number of black squares is .
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 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 is odd, color the board like a chessboard with white corners. This coloring satisfies the requirements of the problem and it has black squares, so the maximum number of black squares is at least .
On the other hand, split the board in 4 parts: one upper-left square, a unit square in the right bottom corner, a rectangle on the right side and a rectangle on the bottom side. Tiling the square with squares and the two rectangles with 2-square dominoes, according with the remarks made at the beginning, one can have at most black squares.
If 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 black squares, so the maximum number of black squares is at least .
Split the board in 9 parts: one square in the middle, four unit squares in the corners and four or rectangles on the borders. Tiling the square with squares and the rectangles with 2-square dominoes, the remarks made at the beginning lead to a maximum of black squares. Hence, if is even, the maximum number of black squares is .
Final answer
If n is odd: (n^2 − 1)/2; if n is even: (n^2 − 4)/2.
Techniques
Coloring schemes, extremal arguments