Japan Mathematical Olympiad

In this answer, the rows are numbered from the top and, the columns are numbered from the left. We denote the cell in the $i$-th row, the $j$-th column by $(i, j)$, $2 \times 2$ square consisting of $(i, j)$, $(i+1, j)$, $(i, j+1)$, $(i+1, j+1)$ by $[i, j]$. Also, a set of cells is said to be mixed, if it has both black and white cells.

First, we consider the case $1 \le k \le n^2$. Let $0 \le a \le n-1$, $1 \le b \le n$ be integers satisfying $k = an + b$. We color cells $(i, j)$ black if $1 \le i \le a$, $1 \le j \le n$ or $i = a+1$, $1 \le j \le b$ and color the other cells white. In this coloring, $[i, j]$ is mixed if and only if $1 \le i \le a$, $j = n$ or $i = a$, $b \le j < n$, or $i = a+1$, $1 \le j \le b$. Hence, the number of mixed $2 \times 2$ squares is $b$ if $a = 0$, $n+a$ if $a \ge 1$. Therefore, $k \le n^2 - n$ does not satisfy the condition in the problem statement, while for $n^2 - n + 1 \le k \le n^2$, we can color the board such that there are exactly $2n-1$ mixed $2 \times 2$ squares.

Secondly, we consider the case $n^2 - n + 1 \le k \le 2n^2$. We show that there exist at least $2n-1$ mixed $2 \times 2$ squares in this case. In the case that all rows are mixed, there exists $1 \le j < 2n$ for any $1 \le i < 2n$ such that the colors of $(i, j)$ and $(i, j+1)$ are different, and $[i, j]$ is mixed for such $j$. Hence, the number of mixed $2 \times 2$ squares is at least $2n-1$. Similarly, this argument works also in the case all columns are mixed. Therefore, we only have to check the case when there exist a row and a column whose all cells have the same color. We show the following lemma.

Lemma. Let $R, C$ be positive integers. Each cell in a $R \times C$ board is colored black or white. If all cells in the first row and the first column have the same color, and there are $m$ cells which have the other color, the number of mixed $2 \times 2$ squares is at least $2\sqrt{m} - 1$.

Proof. Since the case $m=0$ is trivial, we assume that $m \ge 1$. When the number of mixed rows is $a$ and the number of mixed columns is $b$, we show that there exist at least $a+b-1$ mixed $2 \times 2$ squares. Since rows and columns are mixed if they have a cell whose color is different from that of the top left cell, $ab \ge m$ holds. We only have to show it since $a+b \ge 2\sqrt{ab} \ge 2\sqrt{m}$ by AM-GM inequality.

We create a graph $G$ whose vertices are mixed $2 \times 2$ squares and the set of edges are defined as follows. (The terms of graph theory in the following are explained at the end of this answer.)

For each integer $1 < i < R$, if the $i$-th row is mixed, we choose an integer $1 \le j < C$ such that $(i, j)$ and $(i, j+1)$ have different colors and connect $[i-1, j]$ and $[i, j]$ by an edge. Similarly, for each integer $1 < j < C$, if the $j$-th column is mixed, we choose an integer $1 \le i < R$ such that $(i, j)$ and $(i+1, j)$ have different colors and connect $[i, j-1]$ and $[i, j]$ by an edge.

We show that $G$ has no cycle. Take any edge in $G$. Without loss of generality, we can assume that this edge connects $[i-1, j]$ and $[i, j]$ for some $1 < i < R$ and $1 \le j < C$. By the definition of the set of edge of $G$, none of the other edges connect a $2 \times 2$ square located in the 1st to $i$-th rows and a $2 \times 2$ square located in the $i$-th to $R$-th rows, from which $G$ has no cycle.

$G$ has at least one vertex by $m \ge 1$. Since $G$ has no cycle, each connected component of $G$ is a tree, and the number of the vertices is bigger than that of the edges exactly by 1. Therefore, denoting the number of the vertices and the edges and the connected components of $G$ by $V$, $E$, $C$ respectively, we have $V = E + C$. By the definition of the set of edges, $E \ge (a-1) + (b-1)$ holds and, combined with $C \ge 1$, we have $V \ge a+b-1$, which is what we wanted to show. ■

We take $1 \le i, j, \le 2n$ such that all the cells in the $i$-th row and $j$-th column have the same color. We denote the number of cells with the other color
* in the 1st to $i$-th rows, the 1st to $j$-th columns by $a$,
* in the 1st to $i$-th rows, the $j$-th to $2n$-th columns by $b$,
* in the $i$-th to $2n$-th rows, the 1st to $j$-th columns by $c$,
* in the $i$-th to $2n$-th rows, the $j$-th to $2n$-th columns by $d$.

Denoting $\max\{0, 2\sqrt{m} - 1\}$ by $f(m)$, the number of mixed $2 \times 2$ squares is at least $f(a) + f(b) + f(c) + f(d)$ by the lemma. We define $g(m) = \frac{f(m)}{m}$ for $m \ge 1$ and $g(0) = g(1) = 1$. Then, $f$ is weakly monotonically increasing and $f(m) = mg(m)$ for any $m \ge 0$. Also, since for any $1 \le l \le m$,
$$\begin{aligned} g(m) - g(l) &= \frac{2\sqrt{m} - 1}{m} - \frac{2\sqrt{l} - 1}{l} \\ &= \left( \frac{2}{\sqrt{m}} - \frac{2}{\sqrt{l}} \right) - \left( \frac{1}{m} - \frac{1}{l} \right) \\ &= \left( \frac{2}{\sqrt{m}} - \frac{2}{\sqrt{l}} \right) \left( 1 - \left( \frac{1}{2\sqrt{m}} + \frac{1}{2\sqrt{l}} \right) \right) \\ &\le 0 \end{aligned}$$

equals to $k$ or $4n^2 - k$, we have $a+b+c+d \ge k \ge n^2 - n + 1$ by $n^2 - n + 1 \le k \le 2n^2$ and have
$$\begin{aligned} f(a) + f(b) + f(c) + f(d) \\ &= ag(a) + bg(b) + cg(c) + dg(d) \\ &\ge ag(a+b+c+d) + bg(a+b+c+d) + cg(a+b+c+d) + dg(a+b+c+d) \\ &= (a+b+c+d)g(a+b+c+d) \\ &= f(a+b+c+d) \\ &\ge f(n^2 - n + 1) \\ &> 2n - 2. \end{aligned}$$

Therefore, there exist at least $2n-1$ mixed $2 \times 2$ squares. Especially, for $k$ in $n^2-n+1 \le k \le n^2$ satisfy the condition in the problem statement.

Lastly, we consider the case $n^2 + 1 \le k \le 2n^2$. We show that $k$ is a multiple of $2n$ if the number of the mixed $2 \times 2$ squares is $2n-1$. Since the case $n=1$ is obvious, we assume that $n \ge 2$.

If all cells in a row and a column have the same color, the argument above shows that there exist at least $f(k)$ mixed $2 \times 2$ squares. By $f(k) > 2n-1$, this case is excluded. Hence, without loss of generality, we can assume that all the rows are mixed. In this case, for any $1 \le i < 2n$, there exists exactly one $1 \le j < 2n$ such that $[i, j]$ is mixed. Therefore, for any $1 \le i \le 2n$, there exists exactly one $1 \le j < 2n$ such that $(i, j)$ and $(i, j+1)$ have different colors and $j$ is the same value for any $i$. The shared value $j$ is denoted simply by $j$. If $(i, 1)$ and $(i+1, 1)$ have different colors for some $1 \le i < 2n$, $(i, 2n)$ and $(i+1, 2n)$ also have different colors and both $[i, 1]$ and $[i, 2n-1]$ are mixed, which contradicts since $n \ge 2$. Therefore, since $(i, 1)$ and $(i+1, 1)$ have the same color for any $1 \le i < 2n$, the number of the cells which have the same color as $(1, 1)$ is $2jn$ and the number of the cells which have the same color as $(1, 2n)$ is $2n(2n-j)$, which shows that $k$ is a multiple of $2n$.

We assume that $k$ is a multiple of $2n$ and $a = \frac{k}{2n}$. When the cell in the 1st to $a$-th columns are colored black and the other cells are colored white, the number of mixed $2 \times 2$ squares is $2n-1$. Therefore, in the case $n^2 + 1 \le k \le 2n^2$, the condition in the problem statement is satisfied if and only if $k$ is a multiple of $2n$.

From all the arguments above, the values $k$ which satisfy the condition in the problem statements are all $n^2-n+1 \le k \le n^2$ and all multiples of $2n$ in $n^2+1 \le k \le 2n^2$.