Maths Olympiad Prep

Library / /96 of 115

Number theory Difficulty 7.6 National olympiad, round 2 Find the answer

Let p1,p2,p3,...p_1,p_2,p_3,... be the prime numbers listed in increasing order, and let x0x_0 be a real number between 00 and 11 . For positive integer kk , define
xk={0 if xk1=0{pkxk1} if xk10x_{k}=\begin{cases}0&\text{ if }x_{k-1}=0\\ \left\{\frac{p_{k}}{x_{k-1}}\right\}&\text{ if }x_{k-1}\ne0\end{cases}
where {x}\{x\} denotes the fractional part of xx . (The fractional part of xx is given by xxx-\lfloor{x}\rfloor where x\lfloor{x}\rfloor is the greatest integer less than or equal to xx .) Find, with proof, all x0x_0 satisfying 0<x0<10<x_0<1 for which the sequence x0,x1,x2,...x_0,x_1,x_2,... eventually becomes 00 .

A number or a short expression. Spacing and $ signs are ignored.

Solution

All rational numbers between 0 and 1 inclusive will eventually yield some xk=0x_k = 0 . To begin, note that by definition, all rational numbers can be written as a quotient of coprime integers. Let x0=mnx_0 = \frac{m}{n} , where m,nm,n are coprime positive integers. Since 0<x0<10<x_0<1 , 0<m<n0<m<n . Now x1={p1mn}={np1m}.x_1 = \left\{\frac{p_1}{\frac{m}{n}}\right\}=\left\{\frac{np_1}{m}\right\}. From this, we can see that applying the iterative process will decrease the value of the denominator, since m<nm<n . Moreover, the numerator is always smaller than the denominator, thanks to the fractional part operator. So we have a strictly decreasing denominator that bounds the numerator. Thus, the numerator will eventually become 0.
On the other hand, if x0x_0 is irrational, then a simple induction will show that xkx_k will always be irrational. Indeed, the base case has been established, and, if xkx_k is irrational, then pk+1xk\dfrac{p_{k+1}}{x_k} must be too, and likewise for its fractional portion, which differs from it by an integer. Hence xk+1x_{k+1} is irrational, completing the proof.

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

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.