2018 IMO Problems/Problem 5
Problem
Let be an infinite sequence of positive integers. Suppose that there is an integer such that, for each , the number is an integer. Prove that there is a positive integer such that for all
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 is an integer for all . We proceed by -adic valuation only henceforth.
[b][color=red]Claim:[/color][/b] If , then for .
[i]Proof.[/i] The first two terms of have nonnegative , so we need .
[b][color=red]Claim:[/color][/b] If , then is eventually constant.
[i]Proof.[/i] By hypothesis . We consider two cases. [list] [*]First assume for some . We claim that for any we have: This is just by induction on ; from , we have which implies the displayed inequality (since otherwise exactly one term of has nonnegative ). Thus once we reach this case, is monotic but bounded below by , and so it is eventually constant.
[*]Now assume for every . Take any then. We have , and also , so among the three terms of , two must have equal -adic valuation. We consider all three possibilities: \begin{align*} \nu_p\left(\frac{a_{n+1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_1}\right) &\implies \boxed{\nu_p(a_{n+1}) = \nu_p(a_{n})} \\ \nu_p\left(\frac{a_{n+1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right) &\implies \boxed{\nu_p(a_{n+1}) = \frac{\nu_p(a_n) + \nu_p(a_1)}{2}} \\ \nu_p\left(\frac{a_{n}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right) &\implies \nu_p(a_{n+1}) = \nu_p(a_1),\text{ but this is impossible}. \end{align*} Thus, and is bounded above by . So in this case we must also stabilize. \qedhere [/list]
Since the latter claim is applied only to finitely many primes, after some time is fixed for all . Afterwards, the sequence satisfies for each , and thus must be eventually constant.
[b][color=red]Remark:[/color][/b] This solution is almost completely -adic, in the sense that I think a similar result if one replaces by for any particular prime . In other words, the primes almost do not talk to each other.
There is one caveat: if is an integer sequence such that is eventually constant for each prime then may not be constant. For example, take to be the 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
See Also
2018 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |