Putnam 1998/A4 solution

Putnam 1998

Problem A4

Define the sequence of decimal integers a_n as follows: a₁ = 0; a₂ = 1; a_n+2 is obtained by writing the digits of a_n+1 immediately followed by those of a_n. When is a_n a multiple of 11?

Solution

Answer: n = 1 (mod 6).

Easy.

Recall that if n = d_md_m-1...d₁d₀, where the d_i are decimal digits, then the residue of n mod 11 is f(n) = (d₀ + d₂ + ... ) - (d₁ + d₃ + ... ). A trivial induction shows that a_n has an odd number of digits unless n is a multiple of 3. Hence f(a_n) = -f(a_n-1) + f(a_n-2) unless n = 2 (mod 3) when f(a_n) = f(a_n-1) + f(a_n-2). Another simple induction shows that f(a_n) = 1 for n = 0, 2, 5 (mod 6), -1 for n = 3 (mod 6), 2 for n = 4 (mod 6), and 0 for n = 1 (mod 6).

Putnam 1998