We call a coloring of a $2022 \times 2022$ checkerboard a banger coloring if it is colored by $2$ colors, black and white, such that each $2 \times 2$ square contains an even number of black cells. The number of banger colorings is $b$. Let $b = b_1b_2... cd$ (so $d$ is the last digit of $b$ and $c$ is the $2$nd last digit of $b$). Enter $c^2 + d^2 + 5$.
Problem
Source:
Tags: combinatorics, Coloring
IbrahimNadeem
10.01.2024 09:14
Let the number of banger colorings of an $n \times n$ checkerboard be $b_n$. We count and see that $b_1 = 1$ and $b_2 = 8$. Then create a diagram of an $(n+1) \times (n+1)$ checkerboard. We can split this into an $n \times n$ checkerboard, two $1\times n$ rows, and a single square at the corner. Note that there are exactly $2$ ways to color in each of the rows, since we can choose either black or white for the end of the row and then determine the rest to satisfy the 'even number' requirement. The final corner square is determined in exactly $1$ way, so $b_{n+1} = 4b_n$.
Therefore, $b_{2022} = 4^{2020} \cdot 8 = 2^{4043}$. By Euler's Totient Theorem, $\phi(25) = 20 \Rightarrow 2^{4043} \equiv 2^3 \equiv 8 \pmod{25}$. Since $2^{4043} \equiv 0\pmod{4}$, we solve this recurrence to find that the last two digits of $b$ are $08$. So $c^2 + d^2 + 5 = \boxed{69}$ (hehe funni)
Jishnu4414l
12.02.2024 06:34
Notice that in a $2x2$ square, coloring any three squares decides the color of the fourth. We now begin coloring from the $2x2$ square at the top right of the checkerboard. There are $2^3$ ways to color this square. Now we color the extreme row and column associated with the $2x2$ square. There are $2^{2020}\times 2^{2020}$ ways to do this. It is not hard to see that coloring only the aforementioned cells decides the color of the whole checkerboard. So the number of banger colorings of the checker board is $2^{4043}$. We see that $2^{4043} \equiv 0 \pmod 4$ Now as $\phi(25)=20$, using Euler's theorem we have $2^{20}\equiv 1 \pmod {25} \implies 2^{4043} \equiv 2^3 \equiv 8 \pmod {25}$. We now see that $2^{4043} \equiv 08 \mod 100$. So $c^2+d^2+5=69$.