Difference between revisions of "1997 USAMO Problems/Problem 1"

(Solution)
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 +
== Problem ==
 +
Let <math>p_1,p_2,p_3,...</math> be the prime numbers listed in increasing order, and let <math>x_0</math> be a real number between <math>0</math> and <math>1</math>. For positive integer <math>k</math>, define
  
 +
<math> x_{k}={0 if xk1=0{pkxk1} if xk10 </math>
 +
 +
where <math>\{x\}</math> denotes the fractional part of <math>x</math>. (The fractional part of <math>x</math> is given by <math>x-\lfloor{x}\rfloor</math> where <math>\lfloor{x}\rfloor</math> is the greatest integer less than or equal to <math>x</math>.) Find, with proof, all <math>x_0</math> satisfying <math>0<x_0<1</math> for which the sequence <math>x_0,x_1,x_2,...</math> eventually becomes <math>0</math>.
 +
 +
== Solution ==
 +
 +
All rational numbers between 0 and 1 inclusive will eventually yield some <math>x_k = 0</math>. To begin, note that by definition, all rational numbers can be written as a quotient of coprime integers. Let <math>x_0 = \frac{m}{n}</math>, where <math>m,n</math> are coprime positive integers. Since <math>0<x_0<1</math>, <math>0<m<n</math>. Now <cmath>x_1 = \left\{\frac{p_1}{\frac{m}{n}}\right\}=\left\{\frac{np_1}{m}\right\}.</cmath> From this, we can see that applying the iterative process will decrease the value of the denominator, since <math>m<n</math>. 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 <math>x_0</math> is irrational, then a simple induction will show that <math>x_k</math> will always be irrational. Indeed, the base case has been established, and, if <math>x_k</math> is irrational, then <math>\dfrac{p_{k+1}}{x_k}</math> must be too, and likewise for its fractional portion, which differs from it by an integer. Hence <math>x_{k+1}</math> is irrational, completing the proof.
 +
 +
== See Also ==
 +
{{USAMO newbox|year=1997|before=First Question|num-a=2}}
 +
 +
[[Category:Olympiad Number Theory Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:14, 13 February 2015

Problem

Let $p_1,p_2,p_3,...$ be the prime numbers listed in increasing order, and let $x_0$ be a real number between $0$ and $1$. For positive integer $k$, define

$x_{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\}$ 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,...$ eventually becomes $0$.

Solution

All rational numbers between 0 and 1 inclusive will eventually yield some $x_k = 0$. To begin, note that by definition, all rational numbers can be written as a quotient of coprime integers. Let $x_0 = \frac{m}{n}$, where $m,n$ are coprime positive integers. Since $0<x_0<1$, $0<m<n$. Now \[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<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 $x_0$ is irrational, then a simple induction will show that $x_k$ will always be irrational. Indeed, the base case has been established, and, if $x_k$ is irrational, then $\dfrac{p_{k+1}}{x_k}$ must be too, and likewise for its fractional portion, which differs from it by an integer. Hence $x_{k+1}$ is irrational, completing the proof.

See Also

1997 USAMO (ProblemsResources)
Preceded by
First Question
Followed by
Problem 2
1 2 3 4 5 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png