Difference between revisions of "1997 USAMO Problems/Problem 1"
m (moved Problem 1 to 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}= | ||
+ | |||
+ | 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 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.