Here's to a prolific winter-break USAMO marathon
by shiningsunnyday, Dec 10, 2016, 10:52 AM
1997 USAMO P1 wrote:
Let
be the prime numbers listed in increasing order, and let
be a real number between
and
For positive integer
, define
where
denotes the fractional part of
. (The fractional part of
is given by
where
is the greatest integer less than or equal to
.) Find, with proof, all
satisfying
for which the sequence
eventually becomes 





![\[ x_k = \begin{cases} 0 & \mbox{if} \; x_{k-1} = 0, \\[.1in] {\displaystyle \left\{ \frac{p_k}{x_{k-1}} \right\}} & \mbox{if} \; x_{k-1} \neq 0, \end{cases} \]](http://latex.artofproblemsolving.com/e/1/7/e17b3fc5962fba938dee877dac266c3cd024a6e3.png)










Solution
The claim is all rational numbers
Let
where
and
Essentially the main observation is that the denominators
monotonically decreases, since
and
Therefore, at some point we have
and the following term
and the sequence becomes 
Now, for any irrational number, it's well-known that the ring is closed for the binary operations. That is, if
is irrational, no way on earth can
or
be rational, and thus the sequence
will remain irrational, finishing the problem.





![\[x_{k+1} = \left \{ \frac{p_{k+1} n_k}{m_k} \right \} = \frac{p_{k+1}n_k - \text{some integer}}{m_k}\]](http://latex.artofproblemsolving.com/e/0/6/e062b051c866af88279582d309827f438e77c169.png)


![\[x_{j+1} = \left \{ {p_{j+1} n_k} \right \} = 0,\]](http://latex.artofproblemsolving.com/d/5/b/d5bfc87b3f83cbade2078d2ddbf1689ac80335b3.png)

Now, for any irrational number, it's well-known that the ring is closed for the binary operations. That is, if


![\[\frac{p_k}{x_{k-1}} - \left \lfloor \frac{p_k}{x_{k-1}} \right \rfloor\]](http://latex.artofproblemsolving.com/0/6/d/06d2287f57ad15c0d70f8acae83c896566a97b47.png)

Remark
Obviously, the numerators also form a monotonically decreasing sequence. Another way (credit to thecmd999) to show
must be rational is that if
at some point,
is an integer, and thus by induction all the previous terms are rational as well.



Tidbit
Man old USAMO P1/4s are essentially one/two-observation-done, though I should probably still run through all the post-1995 ones in addition to 2/5s over winter break.