Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1997 USAMO Problems/Problem 1: Difference between revisions

← Older editNewer edit →
added solution
Line 8: Line 8:
== Solution ==
== Solution ==


All rational numbers between 0 and 1 will eventually become 0 under this iterative process. 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.
All rational numbers between 0 and 1 will eventually become 0 under this iterative process. 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, irrational <math>x_0</math> will never become 0, because <math>x_k</math> will always be irrational.
On the other hand, irrational <math>x_0</math> will never become 0, because <math>x_k</math> will always be irrational.

Revision as of 05:12, 3 August 2013

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 will eventually become 0 under this iterative process. 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, irrational $x_0$ will never become 0, because $x_k$ will always be irrational.

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. Error creating thumbnail: File missing

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_USAMO_Problems/Problem_1&oldid=56794"