2018 IMO Problems/Problem 5

Problem

Let $a_1, a_2, \dots$ be an infinite sequence of positive integers. Suppose that there is an integer $N > 1$ such that, for each $n \geq N$ , the number $\frac{a_1}{a_2}+\frac{a_2}{a_3}+\dots +\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}$ is an integer. Prove that there is a positive integer $M$ such that $a_m = a_{m+1}$ for all $m \geq M.$

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

The condition implies that the difference $S(n) = \frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ is an integer for all $n > N$ . We proceed by $p$ -adic valuation only henceforth.

[b][color=red]Claim:[/color][/b] If $p \nmid a_1$ , then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ for $n \ge N$ .

[i]Proof.[/i] The first two terms of $S(n)$ have nonnegative $\nu_p$ , so we need $\nu_p(\frac{a_n}{a_{n+1}}) \ge 0$ . $\blacksquare$

[b][color=red]Claim:[/color][/b] If $p \mid a_1$ , then $\nu_p(a_n)$ is eventually constant.

[i]Proof.[/i] By hypothesis $\nu_p(a_1) > 0$ . We consider two cases. [list] [*]First assume $\nu_p(a_k) \ge \nu_p(a_1)$ for some $k > N$ . We claim that for any $n \ge k$ we have: $\nu_p(a_1) \le \nu_p(a_{n+1}) \le \nu_p(a_n).$ This is just by induction on $n$ ; from $\nu(\frac{a_n}{a_1}) \ge 0$ , we have $\nu_p\left( \frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}} \right) \ge 0$ which implies the displayed inequality (since otherwise exactly one term of $S(n)$ has nonnegative $\nu_p$ ). Thus once we reach this case, $\nu_p(a_n)$ is monotic but bounded below by $\nu_p(a_1)$ , and so it is eventually constant.

[*]Now assume $\nu_p(a_k) < \nu_p(a_1)$ for every $k > N$ . Take any $n > N$ then. We have $\nu_p\left(\frac{a_{n+1}}{a_1}\right) < 0$ , and also $\nu_p\left(\frac{a_n}{a_1}\right) < 0$ , so among the three terms of $S(n)$ , two must have equal $p$ -adic valuation. We consider all three possibilities: $\begin{aligned} ν_{p} (\frac{a_{n + 1}}{a_{1}}) = ν_{p} (\frac{a_{n}}{a_{1}}) & ⟹ ν_{p} (a_{n + 1}) = ν_{p} (a_{n}) \\ ν_{p} (\frac{a_{n + 1}}{a_{1}}) = ν_{p} (\frac{a_{n}}{a_{n + 1}}) & ⟹ ν_{p} (a_{n + 1}) = \frac{ν_{p} (a_{n}) + ν_{p} (a_{1})}{2} \\ ν_{p} (\frac{a_{n}}{a_{1}}) = ν_{p} (\frac{a_{n}}{a_{n + 1}}) & ⟹ ν_{p} (a_{n + 1}) = ν_{p} (a_{1}), but this is impossible . \end{aligned}$ Thus, $\nu_p(a_{n+1}) \ge \nu_p(a_n)$ and $\nu_p(a_n)$ is bounded above by $\nu_p(a_1)$ . So in this case we must also stabilize. \qedhere [/list] $\blacksquare$

Since the latter claim is applied only to finitely many primes, after some time $\nu_p(a_n)$ is fixed for all $p \mid a_1$ . Afterwards, the sequence satisfies $a_{n+1} \mid a_n$ for each $n$ , and thus must be eventually constant.

[b][color=red]Remark:[/color][/b] This solution is almost completely $p$ -adic, in the sense that I think a similar result if one replaces $a_n \in {\mathbb Z}$ by $a_n \in {\mathbb Z}_p$ for any particular prime $p$ . In other words, the primes almost do not talk to each other.

There is one caveat: if $x_n$ is an integer sequence such that $\nu_p(x_n)$ is eventually constant for each prime then $x_n$ may not be constant. For example, take $x_n$ to be the $n$ th prime! That's why in the first claim (applied to co-finitely many of the primes), we need the stronger non-decreasing condition, rather than just eventually constant

2018 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search

2018 IMO Problems/Problem 5

Problem

Solution

See Also