Difference between revisions of "2018 IMO Problems/Problem 5"
(Created page with "Let <math>a_1, a_2, \dots</math> be an infinite sequence of positive integers. Suppose that there is an integer<math> N > 1</math> such that, for each <math>n \geq N</math>, t...") |
(→Solution) |
||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
+ | |||
Let <math>a_1, a_2, \dots</math> be an infinite sequence of positive integers. Suppose that there is an integer<math> N > 1</math> such that, for each <math>n \geq N</math>, the number <math>\frac{a_1}{a_2}+\frac{a_2}{a_3}+\dots +\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}</math> is an integer. Prove that there is a positive integer <math>M</math> such that <math>a_m = a_{m+1}</math> for all <math>m \geq M.</math> | Let <math>a_1, a_2, \dots</math> be an infinite sequence of positive integers. Suppose that there is an integer<math> N > 1</math> such that, for each <math>n \geq N</math>, the number <math>\frac{a_1}{a_2}+\frac{a_2}{a_3}+\dots +\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}</math> is an integer. Prove that there is a positive integer <math>M</math> such that <math>a_m = a_{m+1}</math> for all <math>m \geq M.</math> | ||
+ | |||
+ | ==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: | ||
+ | |||
+ | 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== | ||
+ | |||
+ | {{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:
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 |