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

**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}=3{A}_{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}=3{A}_{n}$, we obtain $3{A}_{n}=3(3{A}_{n-1}+3{A}_{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 (3{d}_{n}+4{d}_{n}^{\prime})$, hence ${d}_{n+1}^{\prime}=3{d}_{n}+4{d}_{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\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$ and ${d}_{1}^{\prime}=19\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$. Then, ${d}_{n+1}^{\prime}=3{d}_{n}+4{d}_{n}^{\prime}\equiv {d}_{n}^{\prime}\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$. Therefore, by induction, ${d}_{n}^{\prime}\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$ for any $n$. Then, ${d}_{n+1}={d}_{n}+{d}_{n}^{\prime}\equiv {d}_{n}+1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$. From this, proceeding by induction, we can deduce that ${d}_{n}\equiv n+1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$.

Now, this immediately gives us that ${d}_{25}\equiv 2\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}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\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}6)$ (because when ${d}_{k}\equiv 0\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}3)$ for $k\equiv 2\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}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.