### New Zealand, Camp Selection 2018, problem 7

June 29, 2019

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

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

Solution. We are going to use induction. Instead of the rectangle $2×50$$2 \times 50$, we consider a rectangle $2×n$$2 \times n$; and let ${A}_{n}$$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}$$A_{50}$. In addition to ${A}_{n}$$A_n$, we introduce ${B}_{n}$$B_n$ as the number of ways to color the cells of $2×n$$2 \times n$ with the specified condition and such that the rightmost column (both cells in this column) is red; and ${C}_{n}$$C_n$ as the number of ways to color the cells of $2×n$$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}$$A_n=B_n+C_n$.

We can directly check that ${B}_{1}=1$$B_1 = 1$ and ${C}_{1}=3$$C_1 = 3$.

Now, consider what happens when we add an additional column to the rectangle on the right, thus going from $2×n$$2 \times n$ to $2×\left(n+1\right)$$2 \times (n+1)$. For ${B}_{n+1}$$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×2$$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}$$B_{n+1} = C_n$.

For ${C}_{n+1}$$C_{n+1}$, we have $3$$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×2$$2 \times 2$ is satisfied no matter how the second from the right column is colored. Therefore, ${C}_{n+1}=3{A}_{n}=3\left({B}_{n}+{C}_{n}\right)$$C_{n+1}=3A_n = 3(B_n+C_n)$.

Since ${B}_{n}={C}_{n-1}$$B_{n}=C_{n-1}$, we obtain ${C}_{n+1}=3\left({B}_{n}+{C}_{n}\right)=3\left({C}_{n}+{C}_{n-1}\right)$$C_{n+1}=3(B_n+C_n)=3(C_n+C_{n-1})$. Now, since ${C}_{n+1}=3{A}_{n}$$C_{n+1}=3A_n$, we obtain $3{A}_{n}=3\left(3{A}_{n-1}+3{A}_{n-2}\right)$$3A_n=3(3A_{n-1}+3A_{n-2})$, or ${A}_{n}=3\left({A}_{n-1}+{A}_{n-2}\right)$$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$: ${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$$3$ that ${A}_{n}$$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}$$d_n$ and ${d}_{n}^{\prime }$$d_n'$ such that ${A}_{2n}={3}^{n}\cdot {d}_{n}$$A_{2n}=3^n \cdot d_n$ and ${A}_{2n+1}={3}^{n}\cdot {d}_{n}^{\prime }$$A_{2n+1}=3^n \cdot d_n'$ (in the definition, we are not assuming that ${d}_{n}$$d_n$ and ${d}_{n}^{\prime }$$d_n'$ are integer numbers, we would need to prove it).

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

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

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

Now, let us consider ${d}_{n}$$d_n$ and ${d}_{n}^{\prime }$$d_n'$ modulo $3$$3$. We see that ${d}_{1}=5\equiv 2\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_1=5 \equiv 2 \pmod 3$ and ${d}_{1}^{\prime }=19\equiv 1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_1'=19 \equiv 1 \pmod 3$. Then, ${d}_{n+1}^{\prime }=3{d}_{n}+4{d}_{n}^{\prime }\equiv {d}_{n}^{\prime }\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_{n+1}'=3d_n+4d_n' \equiv d_n' \pmod 3$. Therefore, by induction, ${d}_{n}^{\prime }\equiv 1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_n' \equiv 1 \pmod 3$ for any $n$$n$. Then, ${d}_{n+1}={d}_{n}+{d}_{n}^{\prime }\equiv {d}_{n}+1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_{n+1}=d_n+d_n' \equiv d_n+1 \pmod 3$. From this, proceeding by induction, we can deduce that ${d}_{n}\equiv n+1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_n \equiv n+1 \pmod 3$.

Now, this immediately gives us that ${d}_{25}\equiv 2\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3\right)$$d_{25} \equiv 2 \pmod 3$, and thus ${A}_{50}={3}^{25}\cdot {d}_{25}$$A_{50}=3^{25} \cdot d_{25}$ is a multiple of ${3}^{25}$$3^{25}$, but not a multiple of ${3}^{26}$$3^{26}$, and we are done.

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