Difference between revisions of "1997 USAMO Problems/Problem 1"
(Blanked the page) |
(→Solution) |
||
(6 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}=\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} </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 13:14, 13 February 2015
Problem
Let be the prime numbers listed in increasing order, and let
be a real number between
and
. For positive integer
, define
where denotes the fractional part of
. (The fractional part of
is given by
where
is the greatest integer less than or equal to
.) Find, with proof, all
satisfying
for which the sequence
eventually becomes
.
Solution
All rational numbers between 0 and 1 inclusive will eventually yield some . To begin, note that by definition, all rational numbers can be written as a quotient of coprime integers. Let
, where
are coprime positive integers. Since
,
. Now
From this, we can see that applying the iterative process will decrease the value of the denominator, since
. 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 is irrational, then a simple induction will show that
will always be irrational. Indeed, the base case has been established, and, if
is irrational, then
must be too, and likewise for its fractional portion, which differs from it by an integer. Hence
is irrational, completing the proof.
See Also
1997 USAMO (Problems • Resources) | ||
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.