Library / Iranian Mathematical Olympiad /216 of 270

Iranian Mathematical Olympiad

Number theory Difficulty 7.2 National Olympiad, round 2 Prove it Iran

For a sequence of positive integers $x_1, x_2, \dots$ , we perform the following operation: In the $i$ -th step, we mark all rational numbers in the interval $[0, 1]$ with denominator $x_i$ (i.e., numbers of the form $j/x_i$ for $j \in \{0, 1, \dots, x_i\}$ ). Let $a_i$ be the length of the shortest interval whose two endpoints have been marked up to step $i$ . Find all sequences $x_1, x_2, \dots$ such that $x_5 = 5$ and for every natural number $n$ , we have:
$a_1 + a_2 + \dots + a_n = 2 - \frac{1}{x_n}$

Solution

First, note that since $a_1 + a_2 + \cdots + a_n$ is increasing according to the relation $a_1 + a_2 + \cdots + a_n = \frac{x_n}{n}$ , the sequence $x_n$ must also be increasing. We prove by induction that $a_n = n$ . First, notice that by the problem's condition, it holds up to $n = 5$ . Assume the statement holds for $n$ , and we want to prove it for $n+1$ . For $i < n$ , we have:
$a_i = \frac{1}{i-1} - \frac{1}{i} = \frac{1}{i(i+1)}$
Thus, we have:
$a_{n+1} = 2 - \frac{1}{x_{n+1}} - 2 + \frac{1}{n} = \frac{x_{n+1} - n}{n x_{n+1}}$
Now if $\gcd(x_n, n) = d$ , by Bezout's theorem, we have an interval of length $\frac{d}{n x_{n+1}}$ . Because $d|x_{n+1} - n \rightarrow d \le x_{n+1} - n$ , by assumption, we should have $d = x_{n+1} - n$ . If $d = n k$ , we have
$x_{n+1} = d(k+1) \rightarrow a_{n+1} = \frac{1}{n(k+1)}$
On the other hand:
$a_{n+1} \le \frac{1}{n(n-1)} \implies k+1 \ge n-1 \implies k \ge n-2$
Since $n \ge 5$ and we have $k|n$ , we have $k=n$ , and consequently $x_{n+1} + 1 = n$ . ■

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.