Japan Mathematical Olympiad

$(2n{C}_n{)}^2$ ways

Let us consider the $n\times n$ grid of squares of side length $2$ obtained from the original grid by forming $n^2$ non-overlapping squares of side length $2$ by coalescing $4$ neighboring squares of the original grid into one large square. Let us call each of the squares of the new grid a block. By the condition of the problem, each block contains at most $2$ squares to be colored, and since $2n^2$ squares of the original grid must be colored, we see that exactly $2$ of the $4$ squares in each block must be colored.

Suppose we label $4$ squares in a block $A,B,C,D$ as indicated in the figure below, and do this in the same way for each block.

A	B
C	D

In order to color $2$ of the $4$ squares in a block so as to satisfy the condition of the problem, it is enough to choose one of the squares from $A$ and $D$ and one of the squares from $B$ and $C$ to color. A square in a block can share a side, or a vertex but not a side, or nothing with any square in an adjacent block (which shares with the block a side or just a vertex). Sharing of a vertex but not a side by two squares in adjacent blocks can occur only when the labels of the two squares are $A$ and $D$ or when they are $B$ and $C$.

Therefore, the decision to color which of the squares $A$ and $D$ for a block can be made independently of the decision to color $B$ or $C$ in that block.

Let us now consider how to decide whether $A$ or $D$ should be colored for each block. Let us start off with the block located at the upper-left corner and choose $A$ or $D$ in that block to color, and proceed to the block lying to the immediate right of the initial block on the same row to make the choice between $A$ and $D$ (so as to satisfy the condition of the problem) and keep on doing the same process until we hit the last block on this row, and then go over to the left-most block lying on the second row to repeat the process, going from left to right, and on to the third row, and so on, finally to reach the last block lying at the lower-right corner. In this process, if for some block $X$, the square $D$ was chosen to be colored, then for all of the blocks lying on the same row and to the right of $X$, $D$ should be colored in order to satisfy the condition of the problem. We also see that if there is a row under the row for $X$, then the block lying directly under $X$ must have the square $D$ colored.

Consequently, for each $k=1,2,\dots ,n$, there exists an integer $a_k$ such that in the $k$-th row of the blocks, in all of the $n-a_k$ blocks from the left the square $A$ is colored, while in the remaining $a_k$ blocks in the same row the square $D$ is colored. Furthermore, from the condition on the vertically adjacent pairs of the blocks, we see that $a_k$'s satisfy $$0\le a_1\le a_2\le \cdots \le a_n\le n(†).$$ Conversely, if for such a sequence $\{a_k;1\le k\le n\}$ we color the square $A$ or $D$ in the $k$-th row so that for all of the first $n-a_k$ blocks from the left the square $A$ will be colored and for the remaining $a_k$ blocks in the same row the square $D$ will be colored, and we do this for every $k=1,2,\dots ,n$, then the condition of the coloring will be satisfied as far as the squares $A$ and $D$ are concerned.

If we define, for each $k=1,2,\dots ,n$, $b_k=a_k+k$ the inequalities $(†)$ above are equivalent to $$1\le b_1<b_2<\cdots <b_n\le 2n,$$ and therefore, we see that the number of ways of choosing $A$ or $D$ to color from each of $n^2$ blocks is the same as the number of choosing $n$ distinct integers lying in between $1$ and $2n$ ($1$ and $2n$ inclusive), which equals $2n{C}_n$. The same argument applies to the number of ways of choosing $B$ or $C$ to color, and therefore, the total number of coloring the $2n^2$ squares of the original grid to satisfy the condition of the problem is $(2n{C}_n{)}^2$.