USAMO 1997 Problem1

$p_1, p_2, p_3, \cdots$ を昇順に並んだ素数列とし、$x_0$ を $0 と 1$ の間の実数とする。
正の整数 $k$ に対して、$x_k$ を以下の通り定義する。なお $\{x\}$ で $x$ の小数部を示すものとする。 \[ \begin{eqnarray} x_k = \left\{ \begin{array}{ll} 0 & {\rm if }\; x_{k-1} = 0 \\ \left\{ \frac{p_k}{x_{k-1}}\right\} & {\rm if }\; x_{k-1} \neq 0 \\ \end{array} \right. \nonumber \end{eqnarray} \] このとき、$0<x_0<1$ を満たし、$x_0, x_1, x_2, \cdots$ が $0$ に収束する $x_0$ をすべて見つけよ。

---

$x_0$ を有理数と仮定した場合、互いに素な2つの正の整数 $0 < m_0 < n_0$ が存在し、$x_0 = m_0/n_0$ と表すことができる。
$m_0 < n_0$ であるため、ある正の整数 $\alpha$ が存在し、 \[x_1 = \left\{\frac{p_1}{\frac{m_0}{n_0}}\right\} = \left\{\frac{n_0p_1}{m_0}\right\} = \frac{n_0p_1 - \alpha m_0}{m_0}\] となる。このとき、定義より $0 \leq n_0p_1 - \alpha m_0 < m_0$ を満たす。

ここで改めて、$m_1 = n_0p_1 - \alpha m_0, n_1 = m_0$ とすると、$x_1 = m_1/n_1$ となり、分母は単調減少（$n_0 > m_0 = n_1 > m_1 = \cdots$）となる。
また定義より、分子は分母より常に真に小さくなるため、、分子の数列 $m_i$は $0$ 以上の単調減少となり、$i\to\infty$ としたとき、$m_i\to 0$ となる。

一方、$x_0$ を無理数と仮定した場合、$p_1/x_0$ は無理数であることは自明である。
よって、その小数部である $x_1$ も無理数となる。同様に $x_k$ が無理数ならば、$x_{k+1}$ も無理数となり、$0$ へ収束しない。