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: νp(an+1a1)=νp(ana1)νp(an+1)=νp(an)νp(an+1a1)=νp(anan+1)νp(an+1)=νp(an)+νp(a1)2νp(ana1)=νp(anan+1)νp(an+1)=νp(a1), but this is impossible. 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 $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: νp(an+1a1)=νp(ana1)νp(an+1)=νp(an)νp(an+1a1)=νp(anan+1)νp(an+1)=νp(an)+νp(a1)2νp(ana1)=νp(anan+1)νp(an+1)=νp(a1), but this is impossible. 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

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