17th Iberoamerican 2002 Problem A1 The numbers 1, 2, ... , 2002 are written in order on a blackboard. Then the 1st, 4th, 7th, ... , 3k+1th, ... numbers in the list are erased. Then the 1st, 4th, 7th, ... 3k+1th numbers in the remaining list are erased (leaving 3, 5, 8, 9, 12, ... ). This process is carried out repeatedly until there are no numbers left. What is the last number to be erased? Solution
: 1598. Let a n be the first number remaining after n iterations, so a 0 = 1, a 1 = 2, a 3 = 3, a 4 = 5 etc. We claim that: a n+1 = 3/2 a n if a n is even, and 3/2 (a n + 1) - 1 if a n is odd. We use induction on n. Suppose a n = 2N. Consider the number 3N. There are initially N smaller numbers = 1 mod 3. So after the first iteration, it will lie in 2Nth place. Hence, it will lie in first place after n+1 iterations. Similarly, suppose a n = 2N+1. Consider 3N+2. There are initially N+1 smaller numbers = 1 mod 3. So after the first iteration, it will lie in 2N+1st place. Hence, it will lie in first place after n+1 iterations. That completes the induction. We may now calculate successively the members of the sequence: 1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473, 710, 1065, 1598, 2397. Hence 1598 is the last surviving number from 1, 2, ... , 2002. 17th Ibero 2002 © John Scholes jscholes@kalva.demon.co.uk 19 Oct 2002