Maths Olympiad Prep

Library / /39 of 50

Combinatorics Difficulty 5.9 AIME, harder Prove it Belarus

Let g(n)g(n) be the number of all nn-digit natural numbers each consisting only of the digits 0,1,2,30, 1, 2, 3 (but not necessarily all of them) such that the sum of no two neighboring digits equals 22.
Determine whether g(2010)g(2010) and g(2011)g(2011) are divisible by 1111.
(I. Kozlov)

Solution

Let g0(n)g_0(n), g1(n)g_1(n), g2(n)g_2(n), g3(n)g_3(n) be the quantities of the numbers satisfying the given condition which end by the digits 00, 11, 22, 33 respectively. Then g(n)=g0(n)+g1(n)+g2(n)+g3(n)g(n) = g_0(n) + g_1(n) + g_2(n) + g_3(n). By condition,
g0(n+1)=g0(n)+g1(n)+g3(n)=g(n)g2(n),g1(n+1)=g(n)g1(n),g2(n+1)=g(n)g0(n),g3(n+1)=g(n). \begin{align*} g_0(n+1) &= g_0(n) + g_1(n) + g_3(n) = g(n) - g_2(n), \\ g_1(n+1) &= g(n) - g_1(n), \\ g_2(n+1) &= g(n) - g_0(n), \\ g_3(n+1) &= g(n). \end{align*}
Summing all the equalities, we get
g(n+1)=3g(n)+g3(n)=3g(n)+g(n1). g(n+1) = 3g(n) + g_3(n) = 3g(n) + g(n-1).
Note that modulo 1111 we have g(1)3g(1) \equiv 3, g(2)10g(2) \equiv 10, g(3)0g(3) \equiv 0, g(4)10g(4) \equiv 10, g(5)8g(5) \equiv 8, g(6)1g(6) \equiv 1, g(7)0g(7) \equiv 0, g(8)1g(8) \equiv 1, g(9)3g(9) \equiv 3, g(10)10g(10) \equiv 10. Now we see that residues of the numbers g(n)g(n) modulo 1111 repeat periodically with period 88. So, g(n)0(mod11)g(n) \equiv 0 \pmod{11} iff n3(mod8)n \equiv 3 \pmod{8} or n7(mod8)n \equiv 7 \pmod{8}, whence g(2010)≢0(mod11)g(2010) \not\equiv 0 \pmod{11}, g(2011)0(mod11)g(2011) \equiv 0 \pmod{11}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.