Problem. Let $A_{50}$ be the number of ways to color each cell in a $2\times 50$ rectangle either red or blue such that each $2\times 2$ block contains at least one blue cell. Show that $A_{50}$ is a multiple of $3^{25}$, but not a multiple of $3^{26}$.

Origin: New Zealand, Camp Selection 2018, problem 7.

Solution. We are going to use induction. Instead of the rectangle $2\times 50$, we consider a rectangle $2\times n$; and let $A_n$ be the number of ways to color the cells of this rectangle with the condition specified in the problem setting. So, we are interested in $A_{50}$. In addition to $A_n$, we introduce $B_n$ as the number of ways to color the cells of $2\times n$ with the specified condition and such that the rightmost column (both cells in this column) is red; and $C_n$ as the number of ways to color the cells of $2\times n$ with the specified condition and such that the rightmost column has at least one blue cell. Obviously, we have $A_n=B_n+C_n$.

We can directly check that $B_1=1$ and $C_1=3$.

Now, consider what happens when we add an additional column to the rectangle on the right, thus going from $2\times n$ to $2\times (n+1)$. For $B_{n+1}$, the rightmost column must be red, so there is exactly one possibility for coloring this additional column; and for the rightmost rectangle $2\times 2$ to have a blue cell, the second from the right column must contain at least one blue cell. Therefore, $B_{n+1}=C_n$.

For $C_{n+1}$, we have $3$ possibilities for coloring the rightmost column (both cells blue, or top blue and bottom red, or top red and bottom blue); and the condition for the rightmost rectangle $2\times 2$ is satisfied no matter how the second from the right column is colored. Therefore, $C_{n+1}=3A_n=3(B_n+C_n)$.

Since $B_n=C_{n-1}$, we obtain $C_{n+1}=3(B_n+C_n)=3(C_n+C_{n-1})$. Now, since $C_{n+1}=3A_n$, we obtain $3A_n=3(3A_{n-1}+3A_{n-2})$, or $A_n=3(A_{n-1}+A_{n-2})$.

As a side note, this recurrence relation is similar to the one for the Fibonacci sequence, and it is possible to deduce from it the exact formula for $A_n$: $$A_n=\left(\frac{3\sqrt{13}-1}{2\sqrt{13}}\right)\cdot {\left(\frac{3+\sqrt{13}}{2}\right)}^n+\left(\frac{3\sqrt{13}+1}{2\sqrt{13}}\right)\cdot {\left(\frac{3-\sqrt{13}}{2}\right)}^n.$$ I am not going to get into details of how to obtain this formula, since this formula doesn't really help to find the maximum power of $3$ that $A_n$ is a multiple of; but the technique is the same as for the Fibonacci sequence, which is widely available on the internet.

Back to the original problem, we introduce two additional sequences $d_n$ and $d_n^{\prime }$ such that $A_{2n}=3^n\cdot d_n$ and $A_{2n+1}=3^n\cdot d_n^{\prime }$ (in the definition, we are not assuming that $d_n$ and $d_n^{\prime }$ are integer numbers, we would need to prove it).

We can directly check that $d_1=5$ and $d_1^{\prime }=19$.

Now, we have $A_{2n+2}=3\cdot (A_{2n+1}+A_{2n})=3\cdot (3^n\cdot d_n^{\prime }+3^n\cdot d_n)=3^{n+1}\cdot (d_n+d_n^{\prime })$, hence $d_{n+1}=d_n+d_n^{\prime }$. Also, we have $A_{2n+3}=3\cdot (A_{2n+2}+A_{2n+1})=3\cdot (3^{n+1}\cdot (d_n+d_n^{\prime })+3^n\cdot d_n^{\prime })=3^{n+1}\cdot (3d_n+4d_n^{\prime })$, hence $d_{n+1}^{\prime }=3d_n+4d_n^{\prime }$.

From the two obtained recurrence relations on $d_n$ and $d_n^{\prime }$ and the fact that $d_1$ and $d_1^{\prime }$ are integer numbers, it follows by induction that $d_n$ and $d_n^{\prime }$ are ineteger numbers for any $n$.

Now, let us consider $d_n$ and $d_n^{\prime }$ modulo $3$. We see that $d_1=5\equiv 2(\mathrm{mod}3)$ and $d_1^{\prime }=19\equiv 1(\mathrm{mod}3)$. Then, $d_{n+1}^{\prime }=3d_n+4d_n^{\prime }\equiv d_n^{\prime }(\mathrm{mod}3)$. Therefore, by induction, $d_n^{\prime }\equiv 1(\mathrm{mod}3)$ for any $n$. Then, $d_{n+1}=d_n+d_n^{\prime }\equiv d_n+1(\mathrm{mod}3)$. From this, proceeding by induction, we can deduce that $d_n\equiv n+1(\mathrm{mod}3)$.

Now, this immediately gives us that $d_{25}\equiv 2(\mathrm{mod}3)$, and thus $A_{50}=3^{25}\cdot d_{25}$ is a multiple of $3^{25}$, but not a multiple of $3^{26}$, and we are done.

As a final note, if we consider the general problem for the rectangle $2\times n$, the obtained results give us the maximum power of $3$ that $A_n$ is a multiple of, for any $n$ except when $n\equiv 4(\mathrm{mod}6)$ (because when $d_k\equiv 0(\mathrm{mod}3)$ for $k\equiv 2(\mathrm{mod}3)$, we don't know the maximum power of $3$ that $d_k$ is a multiple of). So, the problem would be more difficult for the rectangle $2\times 52$ than it is for the rectangle $2\times 50$. The readers can think about this remaining part of the general problem.