, 2010

a) Since there are $2^4 = 16 = 4^2$ possibilities to color a $2 \times 2$ square in two colors and a $n \times n$ square contains $(n-1)^2$ such subsquares, we must have $n-1 \ge 4$, or $n \ge 5$. For $n = 5$ a suitable coloring is given in Fig. 20.

Fig. 20

b) Fig. 20 presents a coloring with 10 red squares. We will show that this is the least possible.

Note that in the $5 \times 5$ square there are 4 unit squares in the corners, 12 squares on the sides (not in the corners), and 9 inner squares. Each corner square is contained in exactly one, side square in two and inner square in four $2 \times 2$ squares. All 16 colourings of $2 \times 2$ squares contain a total of 64 unit squares of which 32 are red by symmetry. Therefore, if the $5 \times 5$ square contains $k$ red squares, among them $a$ corner squares, $b$ side squares and $c$ inner squares, then $a + b + c = k$ and $a + 2b + 4c = 32$. The equation $a + 2b + 4c = 32$ implies $c \le 8$. If $c = 8$, then $a = b = 0$. If $c = 7$, then the only possibility to have $k < 10$ is $b = 2$ and $a = 0$. If $c \le 6$, then always $k = a + b + c \ge 10$.

Thus it is enough to show that there are no colorings with required properties with $a = 0$ and $b \le 2$. Indeed, in this case the $5 \times 5$ square has at least two sides not containing any red squares. Without loss of generality, let one of them be the upper side. We saw in part a) that for $n = 5$ each coloring of $2 \times 2$ squares must occur exactly once. Since among all 16 colorings of $2 \times 2$ squares there are 4 such where both upper unit squares are blue, and two upper rows of the $5 \times 5$ square contain exactly $4 \times 2$ squares, all four such colorings must be located in the two upper rows, among these the completely blue coloring. Since the same is true for the other side which does not contain any red squares, the two sides must meet and a completely blue $2 \times 2$ square must be in the corner where the two sides meet. Without loss of generality, let it be the left side. Then the two squares on Fig. 21 must be red, because otherwise there would be more than one completely blue $2 \times 2$ square. But now there are two $2 \times 2$ squares with red square in the lower right corner and the rest of them blue. Therefore there is no coloring satisfying the conditions with $a = 0$ and $b \le 2$ and the least number of red squares is $k = 10$.

Fig. 21