Putnam 1998 Problem A4 Define the sequence of decimal integers a n as follows: a 1 = 0; a 2 = 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
: n = 1 (mod 6). Easy. Recall that if n = d m d m-1 ...d 1 d 0 , where the d i are decimal digits, then the residue of n mod 11 is f(n) = (d 0 + d 2 + ... ) - (d 1 + d 3 + ... ). 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 © John Scholes jscholes@kalva.demon.co.uk 12 Dec 1998