Thursday, February 9, 2006

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.