Smaller... and Smaller... and Smaller. Topic: Monovariants/NT. Level: Olympiad.

Problem: (1997 USAMO - #1) Let $ p_1, p_2, \ldots $ be the prime numbers listed in increasing order, and let $ x_0 $ be a real number between $ 0 $ and $ 1 $. For positive integral $ k $, define

$ x_k $ by $ x_k = 0 $ if $ x_{k-1} = 0 $ and $ x_k = \left\{ \frac{p_k}{x_{k-1}} \right\} $ if $ x_{k-1} \neq 0 $,

where $ \{x\} $ denotes the fractional part of $ x $. (The fractional part of $x$ is given by $x - \lfloor x \rfloor$ where $\lfloor x \rfloor$ is the greatest integer less than or equal to x.) Find, with proof, all $x_0$ satisfying $0 < x_0 < 1$ for which the sequence $x_0, x_1, x_2, \ldots$ eventually becomes $0$.

Solution: We claim that the sequence becomes $ 0 $ iff $ x_0 $ is rational.

First we prove that if $ x_0 $ is irrational then the sequence never becomes $ 0 $.

If $ x_{k-1} $ is irrational, then $ x_k = \left\{\frac{p_k}{x_{k-1}}\right\} $ is clearly irrational as well. So if $ x_0 $ is irrational by induction all $ x_i $ are irrational. Since $ 0 $ is rational, the sequence can never become $ 0 $.

Next we prove that for all rational $ x_0 $, the sequence becomes $ 0 $.

Consider $ x_{k-1} = \frac{a}{b} $ for positive integers $ a,b $ with $ a
--------------------

Comment: Notice that the proof has NOTHING to do with primes. That's rather unusual on olympiads, giving extraneous information, but it was a good way to throw people off. As long as we have a sequence of positive integers (instead of the primes), the proof holds.