Let $p_1, p_2, p_3, \ldots$ 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 & \mbox{if} \; x_{k-1} = 0, \\[.1in] {\displaystyle \left\{ \frac{p_k}{x_{k-1}} \right\}} & \mbox{if} \; x_{k-1} \neq 0, \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, \ldots$ eventually becomes 0.
Problem
Source: USAMO 1997
Tags: floor function, calculus, integration, AMC, USA(J)MO, USAMO, modular arithmetic
24.12.2005 13:51
I don't think we need any property of that sequence $p_i$ except that it's integral... Claim: exactly the rational $x_0$ work. Let $x_0=\frac{a_1}{a_0}$ with $a_1<a_0$. When $x_1=\left\{ \frac{p_1a_0}{a_1} \right\} = \frac{a_2}{a_1}$, we have $a_2<a_1$ again and so on, thus the sequence $a_i$ defined by this is (strictly) decreasing as long as $a_i \neq 0$. But since this is a sequence of non-negative integers, it will become $0$, thus the sequences starting with rational numbers will eventually become $0$. Iff $x_i$ is irrational, also $x_{i+1}$ will be, so for all other starting values it doesn't become $0 \in \mathbb{Q}$.
08.07.2012 05:13
Claim: the sequence goes to $0$ if and only if $x \in \mathbb{Q}$. $\Rightarrow$ direction: suppose that $x = a/b$. Induct on $a+b$. Clearly, the statement is true for $a+b=3 \Rightarrow x=1/2$. Suppose that the claim holds true for all $a+b=k$. Consider $a_1,b_1$ such that $a_1+b_1=k+1$. Notice that in the sequence, $\frac{a_1}{b_1} \rightarrow \frac{b_1 p \bmod a_1}{a_1}$. Since $b_1 p \bmod a_1 < a_1$ and $a_1 < b_1$, we have that $b_1 p \bmod a_1 + a_1 < a_1 + b_1$, so the sequence converges by the inductive hypothesis. $\Leftarrow$ direction: pretty clear that this is true, but to be totally rigorous, suppose that $x \not\in \mathbb{Q}$. If the sequence did eventually converge to $0$, then $x$ could be expressed as $a/b$ for integral $a,b$, implying that $x\in\mathbb{Q}$, a contradiction. This seems too easy for a USAMO problem, even for a #1...
29.04.2013 05:36
We claim that only $x_0 \in \mathbb{Q}$ satisfy the condition. Let $x_k = \frac{p}{q} \neq 0$ for some positive integers $p$ and $q$. Since $0 < x_k < 1$, it follows that $p < q$. Then $x_{k+1} = \left \{ \frac{p_{k+1}}{\frac{p}{q}}\right\}$. Suppose that $p_{k+1} \nmid p$. Then $x_{k+1} = \left\{ \frac{qp_{k+1}}{p} \right \} = \frac{a}{p}$, where $a \equiv qp_{k+1} \pmod{p}$. Now suppose that $p_{k+1} \mid p$. Then $x_{k+1} = \left \{ \frac{q}{b} \right \} = \frac{c}{b}$ where $b = \frac{p}{p_{k+1}}$ and $c \equiv q \pmod{b}$. In both cases, the numerator of $x_k$ is strictly greater than that of $x_{k+1}$; the numerator of nonzero $\{ x_i \}_{i=0}^\infty$ is strictly monovariant. Therefore, the numerator of the numbers of the sequence will become $0$ at some point, implying that the sequence converges to $0$. Now let $x_k \not \in \mathbb{Q}$. Suppose that $x_{k+1}$ is rational. This implies that $\frac{p_{k+1}}{x_k}$ is rational, but this implies that $x_k$ is rational, contradiction. Thus all terms of the sequence are irrational, and will not eventually reach $0$.
27.12.2013 07:33
Looks like I need to start doing nongeo.
29.01.2014 02:00
Lol this is a funny problem.
24.06.2017 03:54
24.08.2017 05:11
First we check that all rational $x_0$ will produce a series that eventually reaches zero. Let the the denominator of $x_0$ be equal to $k$. Clearly, the numerator is less than $k$. When we calculate $x_1$, the new denominator will be less than or equal to$x_0$'s numerator, hence the denominator decreases. It follows that for any choice of $x_0$, there will be some $i$ such that the numerator of $x_i$ is one. It follows that $x_{i+1}=0$. Hence, any rational $x_0$ will eventually terminate. For any irrational $x_k$, note that $x_{k+1}$ will also be irrational. Since an irrational $x_k$ will never fully divide $p_{k+1}$, the series will never terminate, so we are done. $\square$
29.03.2021 18:32
The answer is $x_0$ rational. If $x_0$ is irrational, then all $x_i$ are irrational by induction. So the sequence cannot become zero. If $x_0$ is rational, then all are. Now one simply observes that the denominators of $x_n$ are strictly decreasing, until we reach $0 = \frac 01$. This concludes the proof. Remark: The sequence $p_k$ could have been any sequence of integers.
24.08.2021 03:49
All rationals work. Obviously irrationals fail; otherwise let $x_i = \frac{p_i}{q_i}$ in simplest terms. Observe that $p_i < q_i$ for all $i$, so $$x_{i+1} = \frac k{p_i}$$for some $k < p_i$ by definition. Hence $q_{i+1} < q_i$, and the sequence $q_i$ is decreasing. Therefore, in finitely many terms $q_i$ will become 1, and the next term in the sequence will be 0, as desired.
05.11.2021 22:42
The answer is all rationals. Notice that irrationals fail; therefore we may let $$x_k=\frac{n_k}{d_k},$$where $\gcd{(n_k, d_k)}=1$. Claim: $n_k > n_{k+1}$ when $n_k > 0$. This proves the problem. Proof: Notice that $$x_{k+1}=\left\{\frac{p_{k+1}d_k}{n_k}\right\},$$thus $n_{k+1} < d_{k+1} \leq n_k$. $\blacksquare$
26.04.2022 16:51
I have made a video explanation on this problem: https://youtu.be/OhFyJKqzxlA
19.07.2022 22:40
26.07.2022 21:49
We claim the answer is all rationals. Notice if $x_0$ is irrational, then $x_1,x_2,\dots$ are irrational, and therefore cannot be $0.$ If $x_0$ is rational, all $x_i$ are rational so let $x_{k-1}=m/n.$ Then, $$x_k=\left\{\frac{p_kn}{m}\right\}=\frac{p_kn-\ell m}{m},$$where we choose $\ell$ such that $p_kn-\ell m<m.$ Hence, the numerators of $x_k$ are strictly decreasing, so eventually $x_k=0.$ $\square$
20.09.2022 20:39
07.04.2023 04:47
The answer is $X_0$ can be any rational number between $[0,1)$ Observe that $\frac{P_k}{X_{k-1}}$ needs to be an integer so $X_{k-1}$ must be rational. For $X_{k-1}$ to be rational, then $X_{k-2}$ must also be rational, then so on until $X_0$. Set $X_k=\frac{a}{b}$. $X_{k+1}=\frac{b*P_{k+1}}{a}$ which must have a denominator of $a$, which is also less than $b$. Note that we want $X_k=\frac{1}{b}$, for any positive integer $b$, so that $X_{k+1}$ is an integer. Note that since the denominator of $X_k$ is strictly decreasing and that $0 \le X_n < 1$ for all whole numbers $n$, the sequence must eventually contain an element having a numerator of 1, hence implying our claim. $\blacksquare$
07.04.2023 05:28
28.05.2024 19:38
We claim the answer is all rational $0 < x_0 < 1$. Clearly if $x_0$ is irrational, all operations preserve irrationality so the sequence never becomes all $0$. Now suppose $x_0$ is rational, at any point $x_k = \dfrac{a}{b}$ where $a, b \in \mathbb{Z}^{+}$, $\gcd(a, b) = 1$ and $1 \le a < b$, we have $x_{k + 1} = \left\{\frac{p_{k + 1} b}{a} \right\}$ which implies when $x_{k + 1}$ is fully simplified its denominator is at most $a$. Then as the sequence progresses the denominator always decreases when fully simplified, so at some point it terminates to all zeroes.
30.12.2024 19:17
If $x_0$ is irrational, then $x_1=\left \{ \frac{p_{1}}{x_0} \right \}$ is irrational. Similarly $x_2$ is irrational and so on. Thus every element of $\{x_i\}$ is irrational. Since $0$ is rational, the sequence will never 0 out. If $x_0=\frac{n}{m}$ for $\gcd(n,m)=1$ and $n>m \in \mathbb Z$, then $x_1=\left \{ \frac{p_{1}}{x_0} \right \}=\left \{ \frac{p_1m}{n} \right \}=\frac{p_1m \mod {n}}{n}$. Let $b_1=p_1m \mod{n}$, clearly $b_1<n$. We can see that the sequence of numerators would go like $b_1=p_1m \mod{n}, b_2=p_2 n \mod{b_1}, b_3=b_1p_3 \mod{b_2}, \ldots, b_i=b_{i-2}p_i \mod{b_{i-1}}, \ldots$ This is a monotonically decreasing sequence of nonnegative integers, so it must eventually go to 0 at some point. Thus every rational number between 0,1 works.