Hard Grid Arrangement

Question

Consider an $n	imes n$ grid where each cell can be filled with either 0 or 1. How many such arrangements are there such that the sum of the cells in every $2	imes2$ sub-grid is equal to 2?

Express your answer as a closed-form formula in terms of $n$. Enter the answer for $n=10$.

QuantSoc · Accepted Answer

Consider the arrangement of the first row of the grid. There are $2^n$ possible ways to fill the first row, as each cell can either be 0 or 1.

If the first row is not alternating, it contains two consecutive 0's or two consecutive 1's. Suppose we have 00 in two adjacent columns. To make the corresponding $2	imes2$ sub-grid sum to 2, the cells directly below must be 11. Similarly, 11 forces 00. This determines the entire grid uniquely once the first row is fixed. Therefore, the $2^n-2$ non-alternating first rows each give exactly one valid arrangement.

Now consider an alternating first row. There are exactly two such rows, namely $0101\ldots$ and $1010\ldots$. For an alternating row, the next row can be either of the two alternating patterns, and the same is true independently for every subsequent row. Thus, each alternating first row gives $2^{n-1}$ arrangements.

Hence, the total number of valid arrangements is

$$
(2^n-2)+2\cdot2^{n-1}=2^{n+1}-2.
$$

For $n=10$,

$$
2^{11}-2=2046.
$$