Olympiad Mathematics Again

New Zealand, Camp Selection 2018, problem 7

June 29, 2019

Problem. Let A50 be the number of ways to color each cell in a 2×50 rectangle either red or blue such that each 2×2 block contains at least one blue cell. Show that A50 is a multiple of 325, but not a multiple of 326.

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

Solution. We are going to use induction. Instead of the rectangle 2×50, we consider a rectangle 2×n; and let An 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 A50. In addition to An, we introduce Bn as the number of ways to color the cells of 2×n with the specified condition and such that the rightmost column (both cells in this column) is red; and Cn as the number of ways to color the cells of 2×n with the specified condition and such that the rightmost column has at least one blue cell. Obviously, we have An=Bn+Cn.

We can directly check that B1=1 and C1=3.

Now, consider what happens when we add an additional column to the rectangle on the right, thus going from 2×n to 2×(n+1). For Bn+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 to have a blue cell, the second from the right column must contain at least one blue cell. Therefore, Bn+1=Cn.

For Cn+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×2 is satisfied no matter how the second from the right column is colored. Therefore, Cn+1=3An=3(Bn+Cn).

Since Bn=Cn1, we obtain Cn+1=3(Bn+Cn)=3(Cn+Cn1). Now, since Cn+1=3An, we obtain 3An=3(3An1+3An2), or An=3(An1+An2).

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 An: An=(3131213)(3+132)n+(313+1213)(3132)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 An 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 dn and dn such that A2n=3ndn and A2n+1=3ndn (in the definition, we are not assuming that dn and dn are integer numbers, we would need to prove it).

We can directly check that d1=5 and d1=19.

Now, we have A2n+2=3(A2n+1+A2n)=3(3ndn+3ndn)=3n+1(dn+dn), hence dn+1=dn+dn. Also, we have A2n+3=3(A2n+2+A2n+1)=3(3n+1(dn+dn)+3ndn)=3n+1(3dn+4dn), hence dn+1=3dn+4dn.

From the two obtained recurrence relations on dn and dn and the fact that d1 and d1 are integer numbers, it follows by induction that dn and dn are ineteger numbers for any n.

Now, let us consider dn and dn modulo 3. We see that d1=52(mod3) and d1=191(mod3). Then, dn+1=3dn+4dndn(mod3). Therefore, by induction, dn1(mod3) for any n. Then, dn+1=dn+dndn+1(mod3). From this, proceeding by induction, we can deduce that dnn+1(mod3).

Now, this immediately gives us that d252(mod3), and thus A50=325d25 is a multiple of 325, but not a multiple of 326, and we are done.

As a final note, if we consider the general problem for the rectangle 2×n, the obtained results give us the maximum power of 3 that An is a multiple of, for any n except when n4(mod6) (because when dk0(mod3) for k2(mod3), we don't know the maximum power of 3 that dk is a multiple of). So, the problem would be more difficult for the rectangle 2×52 than it is for the rectangle 2×50. The readers can think about this remaining part of the general problem.