2011 AMC 10A Problem 23

Alice skips $2, 5, 8, \dots$: an arithmetic progression with first term $2$ and common difference $3$. These are the numbers handed to Barbara.

Now observe the general step. If a student receives the progression $a,\ a + d,\ a + 2d,\ \dots$ and groups it in threes, the middle numbers she skips are $a + d,\ a + 4d,\ a + 7d, \dots$: again an arithmetic progression, with first term $a + d$ and difference $3d$. So the list passed on is described by the state
$$(a, d) \longmapsto (a + d,\ 3d).$$

Iterate from Alice's leftover list $(2, 3)$:
- Barbara passes on $(5, 9)$;
- Candice passes on $(14, 27)$;
- Debbie passes on $(41, 81)$;
- Eliza passes on $(122, 243)$;
- Fatima receives $122, 365, 608, 851$ and passes on $(365, 729)$.

The progression $365, 1094, \dots$ has only one term at most $1000$, so the unique number nobody before George says is $365$. (Check with Fatima directly: her group of three is $122, 365, 608$, so she skips $365$; the lone $851$ starts an incomplete group and is said, just as Alice says $1000$.)

The answer is $\boxed{\textbf{(C)}\ 365}$.

Instead of simulating $1000$ numbers, describe the shape of what each student receives: an arithmetic progression, determined by two parameters. The skipping rule acts on those parameters by a simple map, so six rounds are six lines of arithmetic. The first terms $2, 5, 14, 41, 122, 365$ satisfy $a_k = 3a_{k-1} - 1$, i.e. $a_k = \frac{3^k + 1}{2}$; with six students before George and $3^6 = 729 < 1000 < 3^7$, exactly one number survives.

Work backwards from the choices. The numbers Alice skips are $\equiv 2 \pmod 3$; Barbara's skips are $\equiv 5 \pmod 9$; in general the $k$-th student's skips are $\equiv \frac{3^k+1}{2} \pmod{3^k}$. Test $365$: $365 \equiv 2 \pmod 3$, $\equiv 5 \pmod 9$, $\equiv 14 \pmod{27}$, $\equiv 41 \pmod{81}$, $\equiv 122 \pmod{243}$, and $365 = \frac{729+1}{2}$. No other choice passes even the first two tests ($37 \equiv 1$, $242 \equiv 2 \pmod 3$ but $242 \equiv 8 \pmod 9$; $728 \equiv 2 \pmod 3$ but $728 \equiv 8 \pmod 9$; $998 \equiv 2 \pmod 3$ but $998 \equiv 8 \pmod 9$).

• Mis-tracking the last stage: Fatima receives 122, 365, 608, 851 and skips only 365, so answering 122 or 851 (or stopping at Eliza) is wrong.
• Regrouping from $1$ each time (skipping numbers $\equiv 2 \pmod 3$ of the whole range again) instead of grouping each student's own list in threes.
• Choosing $728 = 3^6 - 1$ or $242 = 3^5 - 1$ because the powers of $3$ appear; the survivors are $\frac{3^k + 1}{2}$, not $3^k - 1$.