Let n$\ge$2.Each 1x1 square of a nxn board is colored in black or white such that every black square has at least 3 white neighbors(Two squares are neighbors if they have a common side).What is the maximum number of black squares?
Problem
Source: First Romania JBMO TST 2016
Tags: combinatorics
22.07.2016 23:37
den_thewhitelion wrote: Let $n \geq 2$. Each $1\times 1$ square of a $n\times n$ board is colored in black or white such that every black square has at least $3$ white neighbors (Two squares are neighbors if they have a common side.), What is the maximum number of black squares $?$ Sorry to bumping this, any solution, plz
23.07.2016 00:14
We claim that for even $n$, we can have $\frac{n^2-4}{2}$ black squares, and for odd $n$, we can have $\frac{n^2-1}{2}$. Equality is achieved with a chessboard pattern, but with white squares in the corners (disrupting the chessboard pattern as necessary for $n$ even). Note that the four corner squares must be white, and we can't have two neighbouring black squares along the edges. Given any $2\times2$ square, it can have at most $2$ black squares. For odd $n$, divide the board into four rectangles: an $(n-1)\times(n-1)$ square in the top left corner, a single unit square in the bottom right corner, and two $(n-1)\times1$ rectangles along the edges. Tiling the left square into $2\times2$ sub-grids, and the rectangles into $2\times1$ dominoes, we get at most $\frac{(n-1)^2}{2}+2\cdot\frac{n-1}{2}=\frac{n^2-1}{2}$ black squares, as desired. For even $n$, divide the board into nine rectangles: an $(n-2)\times(n-2)$ square in the middle, four unit squares in the corners, and four $(n-2)\times1$ rectangles along the edges. Tiling the middle square into $2\times2$ sub-grids, and the rectangles into $2\times1$ dominoes, we get at most $\frac{(n-2)^2}{2}+4\cdot\frac{n-2}{2}=\frac{n^2-4}{2}$ black squares, as desired.