Consider a $2024 \times 2024$ grid of unit squares. Two distinct unit squares are adjacent if they share a common side. Each unit square is to be coloured either black or white. Such a colouring is called $\textit{evenish}$ if every unit square in the grid is adjacent to an even number of black unit squares. Determine the number of $\textit{evenish}$ colourings.
Problem
Source: Australia MO 2024 P4
Tags: combinatorics
24.02.2024 22:14
For a n*n square, the answer is 2^n. Rather than white and black, fill the board with zeroes and ones. It’s easy to see that adding two boards módulo 2 gives another good board. Additionally, every good board is determined by the lowest row. So to prove my statement it is enough to prove that every lowest row with only black gives a good arrangement. But after playing around it is evident that it is the case, it creates a rotated rectangle of sorts. For n=5 looks like this: 0000x 000x0 00x00 000x0 00x0x 0x0x0 00x00 0x0x0 x0x0x 0x000 x0x00 0x0x0 x0000 0x000 00x00
24.02.2024 22:22
in above there's n of these rotated rectangles, and they are linearly independent so they span a set of at least 2^n rectangles (adding means toggling) upper bound is because of there is an injection from grid colorings to bottom row colorings
20.06.2024 06:01
if 5×7 what is your answer
07.10.2024 16:19
If you paint the last line randomly, there will be 1 case in each case, so the answer is 2^2024.