A $2019 \times 2019$ square grid is made up of $2019^2$ unit cells. Each cell is coloured either black or white. A colouring is called balanced if, within every square subgrid made up of $k^2$ cells for $1 \le k\le 2019$, the number of black cells differs from the number of white cells by at most one. How many different balanced colourings are there?
(Two colourings are different if there is at least one cell which is black in exactly one of them.)
Let $f(n)$ be the number of different balanced colorings for an $n\times n$ grid. A few unfruitful ideas:
$\mathbf{1) Inclusion-Exclusion}$
Call the event that the $i^{th}$ subgrid is balanced, $B_i$. Then
$$ f(n) = \left | \bigcap B_i \right | = \left | \left( \bigcup (B_i)’ \right)’ \right | = 2^{n^2}-\left | \bigcup (B_i)’ \right|$$
but the latter term isn’t easily calculated.
$\mathbf{ 2) Recursion}$
$f(n)$ will include the number of ways where the top left $(n-1)\times (n-1)$ grid is balanced, but there doesn’t seem to be a fixed $t(n)$ so that $$f(n) = t(n) f(n-1) \ \text{or} \ f(n-1) + t(n) $$
$ \mathbf{3) Manual \ Counting } $
I found $$f(1)=2 \\ f(2) = 6 \\ f(3) = 10 \\ f(4) = 18 \\ f(5)=26 $$
from where I guess $$f(2n+1)= 2^{n+3} -6 $$ but that’s just a guess.
Best Answer
If two adjacent squares in a row have the same colour.
For $2\times2$ balancing, the two columns, $C_1$ and $C_2$, containing these squares must consist of rows of same coloured squares, the colours alternating from row to row.
If there were also two adjacent squares in a column with the same colour then we could make the equivalent statement about the rows, $R_1$ and $R_2$ containing these two squares. But then we would obtain a contradiction where $C_1$ and $C_2$ cross $R_1$ and $R_2$.
Therefore no column contains adjacent same coloured squares and so the colours strictly alternate as one goes down any column and are completely determined by the colours in the top row.
This alternation means that 'even' blocks are automatically balanced whereas an 'odd' block is balanced if and only if its top row is balanced. The top row of the whole grid must therefore consist of alternating runs of white and black squares, each run of length $1$ or $2$, where the colours of the runs of length $2$ must alternate across the row.
From any given run of length $2$, successively pair up the squares on each side and note that all runs of length $2$ will be in one of these pairs. Note also that there will be a single square left on one side or the other.
We can colour the single square with either colour and then as we go across the row we must change colour when we come to a new pair of squares but we can arbitrarily choose the colour of the second square of the pair.
We have $2$ choices for the end of the single square and $2$ choices for its colour. There are then $2^{1009}-1$ choices of colour for the pairs. (Since we are assuming at least one run of $2$ squares we must discard the one choice of colours without such a run.) The total number of boards is $$2^{1011}-4.$$
Otherwise.
We have the same number of boards when two adjacent squares in a column have the same colour. Plus two boards where no adjacent squares have the same colour.
Total number of balanced boards. $$2\times (2^{1011}-4)+2=2^{1012}-6.$$