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
Answer: 1598.
Let an be the first number remaining after n iterations, so a0 = 1, a1 = 2, a3 = 3, a4 = 5 etc. We claim that:
an+1 = 3/2 an if an is even, and 3/2 (an + 1) - 1 if an is odd.We use induction on n. Suppose an = 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 an = 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.
© John Scholes
jscholes@kalva.demon.co.uk
19 Oct 2002