Difference between revisions of "2018 IMO Problems/Problem 5"
(→Solution) |
|||
Line 5: | Line 5: | ||
==Solution== | ==Solution== | ||
{{solution}} | {{solution}} | ||
+ | |||
+ | |||
+ | The condition implies that the difference <math>S(n) = \frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}</math> is an integer for all <math>n > N</math>. We proceed by <math>p</math>-adic valuation only henceforth. | ||
+ | |||
+ | [b][color=red]Claim:[/color][/b] If <math>p \nmid a_1</math>, then <math>\nu_p(a_{n+1}) \le \nu_p(a_n)</math> for <math>n \ge N</math>. | ||
+ | |||
+ | [i]Proof.[/i] The first two terms of <math>S(n)</math> have nonnegative <math>\nu_p</math>, so we need <math>\nu_p(\frac{a_n}{a_{n+1}}) \ge 0</math>. <math>\blacksquare</math> | ||
+ | |||
+ | [b][color=red]Claim:[/color][/b] If <math>p \mid a_1</math>, then <math>\nu_p(a_n)</math> is eventually constant. | ||
+ | |||
+ | [i]Proof.[/i] By hypothesis <math>\nu_p(a_1) > 0</math>. We consider two cases. [list] [*]First assume <math>\nu_p(a_k) \ge \nu_p(a_1)</math> for some <math>k > N</math>. We claim that for any <math>n \ge k</math> we have: <cmath> \nu_p(a_1) \le \nu_p(a_{n+1}) \le \nu_p(a_n). </cmath> This is just by induction on <math>n</math>; from <math>\nu(\frac{a_n}{a_1}) \ge 0</math>, we have <cmath> \nu_p\left( \frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}} \right) \ge 0 </cmath> which implies the displayed inequality (since otherwise exactly one term of <math>S(n)</math> has nonnegative <math>\nu_p</math>). Thus once we reach this case, <math>\nu_p(a_n)</math> is monotic but bounded below by <math>\nu_p(a_1)</math>, and so it is eventually constant. | ||
+ | |||
+ | [*]Now assume <math>\nu_p(a_k) < \nu_p(a_1)</math> for every <math>k > N</math>. Take any <math>n > N</math> then. We have <math>\nu_p\left(\frac{a_{n+1}}{a_1}\right) < 0</math>, and also <math>\nu_p\left(\frac{a_n}{a_1}\right) < 0</math>, so among the three terms of <math>S(n)</math>, two must have equal <math>p</math>-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, <math>\nu_p(a_{n+1}) \ge \nu_p(a_n)</math> and <math>\nu_p(a_n)</math> is bounded above by <math>\nu_p(a_1)</math>. So in this case we must also stabilize. \qedhere [/list] <math>\blacksquare</math> | ||
+ | |||
+ | Since the latter claim is applied only to finitely many primes, after some time <math>\nu_p(a_n)</math> is fixed for all <math>p \mid a_1</math>. Afterwards, the sequence satisfies <math>a_{n+1} \mid a_n</math> for each <math>n</math>, and thus must be eventually constant. | ||
+ | |||
+ | [b][color=red]Remark:[/color][/b] This solution is almost completely <math>p</math>-adic, in the sense that I think a similar result if one replaces <math>a_n \in {\mathbb Z}</math> by <math>a_n \in {\mathbb Z}_p</math> for any particular prime <math>p</math>. In other words, the primes almost do not talk to each other. | ||
+ | |||
+ | There is one caveat: if <math>x_n</math> is an integer sequence such that <math>\nu_p(x_n)</math> is eventually constant for each prime then <math>x_n</math> may not be constant. For example, take <math>x_n</math> to be the <math>n</math>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== | ==See Also== | ||
{{IMO box|year=2018|num-b=4|num-a=6}} | {{IMO box|year=2018|num-b=4|num-a=6}} |
Latest revision as of 13:41, 4 December 2024
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 |