## Problem A1

The numbers $1,2, \ldots, 2002$ are written in order on a blackboard. Then the 1 st, 4 th, 7 th, $\ldots$, $3 \mathrm{k}+1$ th, $\ldots$ numbers in the list are erased. Then the 1 st, $4 \mathrm{th}, 7 \mathrm{th}, \ldots 3 \mathrm{k}+1$ th numbers in the remaining list are erased (leaving $3,5,8,9,12, \ldots$ ). This process is carried out repeatedly until there are no numbers left. What is the last number to be erased?


## Solution

Answer: 1598.

Let $\mathrm{a}_{\mathrm{n}}$ be the first number remaining after $\mathrm{n}$ iterations, so $\mathrm{a}_{0}=1, \mathrm{a}_{1}=2, \mathrm{a}_{3}=3, \mathrm{a}_{4}=5$ etc. We claim that:

```
\(a_{n+1}=3 / 2 a_{n} \quad\) if \(a_{n}\) is even, and
    \(3 / 2\left(a_{n}+1\right)-1\) if \(a_{n}\) is odd.
```

We use induction on $n$. Suppose $a_{n}=2 N$. Consider the number $3 N$. There are initially $\mathrm{N}$ smaller numbers $=1 \mathrm{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 $\mathrm{a}_{\mathrm{n}}=2 \mathrm{~N}+1$. Consider $3 N+2$. There are initially $\mathrm{N}+1$ smaller numbers $=1 \bmod 3$. So after the first iteration, it will lie in $2 \mathrm{~N}+1$ st place. Hence, it will lie in first place after $\mathrm{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, \ldots, 2002$.

