IMO 2018 Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

72 posts

#1 h Jul 10, 2018, 11:19 AM • 26 Y

Y by Durjoy1729, Moaaz, me9hanics, MazeaLarius, Amir Hossein, Davi-8191, naw.ngs, Medjl, adityaguharoy, anantmudgal09, pavel kozlov, khan.academy, centslordm, megarnie, Sprites, jasperE3, myh2910, mathmax12, NO_SQUARES, Adventure10, Mango247, aidan0626, torch, buddyram, deplasmanyollari, Supercali

Let $a_1$ , $a_2$ , $\ldots$ 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} + \cdots + \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$ .

Proposed by Bayarmagnai Gombodorj, Mongolia

This post has been edited 3 times. Last edited by djmathman, Jun 16, 2020, 4:03 AM
Reason: problem author

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Itama

78 posts

Itama

#2 h Jul 10, 2018, 12:08 PM • 4 Y

Y by Kgxtixigct, Adventure10, Mango247, buddyram

I can sence the beauty of the IMO 2018 problems...

Exelent Job!!! problem selection committee & team leaders!!

I would like to know whose problem is this?

This post has been edited 2 times. Last edited by Itama, Jul 10, 2018, 12:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathocean97

606 posts

mathocean97

#3 h Jul 10, 2018, 12:11 PM • 16 Y

Y by e_plus_pi, pieater314159, UK2019Project, Pluto1708, Siddharth03, myh2910, IcCircle, centslordm, megarnie, Nuterrow, mathmax12, Adventure10, Mango247, Zhaom, aidan0626, buddyram

Main claim: If $\frac{a}{x} + \frac{x}{b} - \frac{a}{b}$ is an integer, then $\gcd(a, b) | x.$

Proof: Compute the expression. It becomes $\frac{ab+x^2-ax}{bx}.$ Say a prime $p$ satisfies $p|a, p|b.$ Then $p|x^2$ so $p|x$ . Divide it out and continue.

Now, I will show that as the sequence goes along, that both the numerator and denominator of the reduced fraction $\frac{a_n}{a_1}$ will decrease as $n$ increases past $n \ge N.$

Now, assume that $\frac{a}{x} + \frac{x}{b} - \frac{a}{b}$ is an integer and $\gcd(a, b) = 1.$ Then $x | ab$ so $x = a'b'$ where $a' | a, b' | b$ . Now take $a = a_n, b = a_1, x = a_{n+1}.$ Then $\frac{a_{n+1}}{a_1} = \frac{x}{b} = \frac{a'}{(b/b')}.$ So both the numerator and denominator decreased! Therefore, the sequence $\frac{a_n}{a_1}$ will eventually converge, as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#5 h Jul 10, 2018, 12:39 PM • 23 Y

Y by samoha, Davi-8191, brokendiamond, Mathlover1292, qweDota, rashah76, Abidabi, v4913, Sunnybest, centslordm, megarnie, HamstPan38825, myh2910, Assassino9931, mathmax12, Danielzh, Adventure10, Mango247, buddyram, Sneakyturtle, sky.mty, DEKT, Ali_Vafa

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.

Claim: If $p \nmid a_1$ , then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ for $n \ge N$ .

Proof. 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$

Claim: If $p \mid a_1$ , then $\nu_p(a_n)$ is eventually constant.

Proof. By hypothesis $\nu_p(a_1) > 0$ . We consider two cases.

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{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, $\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

$\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.

Remark: 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.

This post has been edited 6 times. Last edited by v_Enhance, Aug 21, 2018, 2:47 AM
Reason: colorize

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

knm2608

468 posts

knm2608

#6 h Jul 10, 2018, 1:10 PM • 3 Y

Y by adityaguharoy, Adventure10, buddyram

Written a bit hastily, so let me know if there is any flaw.

We have that
$\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1} \in \mathbb{Z} \;\;\; \forall n \geq N \;\;\;\;\;\; (1)$ Now let $m>n$ be an integer and
$A=\frac{a_1}{a_2} + \frac{a_2}{a_3} + \ldots + \frac{a_{n-1}}{a_n}, \;\;\;\; B=\frac{a_n}{a_{n+1}}+\ldots +\frac{a_{m-1}}{a_m}$ Then
$B+\frac{a_m}{a_1}-\frac{a_n}{a_1}\in \mathbb{Z} \;\;\;\;(2)$ Taking $(1)$ from $n$ to $m$ combined with $(2)$ gives
$\frac{a_m}{a_1} \in \mathbb{Z} \; \Rightarrow \frac{a_m}{a_{m+1}}\in \mathbb{Z} \;\;\; \forall m > n$ So $a_{n+1}=ka_1,k\in \mathbb{Z}$ . But
$\frac{a_n}{a_1}\left(1-\frac{1}{k} \right) \in \mathbb{Z}$ So either $k=1$ which implies $a_{n+1}=a_1 \Rightarrow a_m=a_{m+1} \;\; \forall m\geq n+1$ or $a_1|a_n \Rightarrow a_{n+1}|a_n \;\; \forall n$ . In either case we're done.

Edit: It is wrong. Thanks below.

This post has been edited 1 time. Last edited by knm2608, Jul 11, 2018, 12:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kurt Gödel

615 posts

Kurt Gödel

#7 h Jul 10, 2018, 1:43 PM • 4 Y

Y by Doraeminion, Adventure10, Mango247, buddyram

knm2608 wrote:

Taking $(1)$ from $n$ to $m$ combined with $(2)$ gives $\frac{a_m}{a_1} \in \mathbb{Z}$

How? I think (2) is just a repeated application of (1), so it seems like the most you will get out of this is a tautology.

Great problem though!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

WizardMath

2487 posts

WizardMath

#9 h Jul 10, 2018, 2:41 PM • 5 Y

Y by rashah76, Adventure10, Mango247, bhan2025, buddyram

Since the sequence is an integer sequence, the differences of consecutive terms must also be integers. So we have $\frac{a_{n+1}^2-a_n a_{n+1} + a_n a_1}{a_1 a_{n+1}} \in \mathbb{Z}$ Subtracting 1, we have $a_1 a_{n+1} | (a_{n+1} - a_1) (a_{n+1} - a_n)$ . Now consider any prime $p$ that divides $a_1, a_{n}$ . Then we have, by dividing both sides by $p$ , that $p| a_{n+1}$ . Now divide all of $a_1, a_n, a_{n+1}$ by $p$ , and then notice that we can still argue further like this. So $\min ( \nu_p (a_1), \nu_p (a_{n}) ) \le \nu_p(a_{n+1})$ . Since we have $a_1 a_{n+1} | (a_{n+1} - a_1) (a_{n+1} - a_n)$ , we see that $a_{n+1} | a_1 a_n$ .
Note that if $\gcd (a_1, a_{n+1}) = \alpha_{n+1},$ then $a_{n+1} / \alpha_{n+1}$ is an integer, and it divides $a_n$ , so the resulting conjugate factor is $k$ (say). Then $\frac{a_{n+1}}{a_1} = \frac{a_n/k}{a_{1}/\alpha_{n+1}}$ , so the moduli of numerator and denominator are non-increasing. This leads us to $a_m = a_{m+1}$ from some $m$ onwards, since no positive integer sequence can strictly decrease forever.

This post has been edited 2 times. Last edited by WizardMath, Jul 10, 2018, 2:54 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Loppukilpailija

155 posts

Loppukilpailija

#11 h Jul 10, 2018, 3:27 PM • 4 Y

Y by amar_04, Adventure10, Mango247, buddyram

Here's a solution I wrote during the competition. Quite similar to the one written by v_Enhance, but the execution is maybe a little bit bloodier.

Solution:

Proof by contradiction. For the rest of the solution we assume that the sequence $a_n$ isn't constant starting from any point. In the end we will achieve a contradiction, thus proving the statement.

The difference

$\frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}} - \frac{a_n}{a_1} = \frac{a_{n+1}^2 - a_{n+1}a_n + a_na_1}{a_1a_{n+1}}$
is an integer for all $n \ge N$ .

Lemma 1.

There is a prime $p$ such that $v_p(a_{n+1}) \neq v_p(a_n)$ for infinitely many $n \ge N$ .

Proof.

The integer-ness condition above implies that $a_{n+1} \mid a_na_1$ . This means that for all $p \mid a_n$ , $p$ prime and $n \ge N$ , we have either $p \mid a_N$ or $p \mid a_1$ (assume not, and take the smallest $i > N$ for which $p \mid a_i$ ). Thus, there are only finitely many $p$ such that $p \mid a_n$ for some $n \ge N$ . Now, for the statement of the lemma, assume not: now, if we take any prime $p$ which doesn't divide any of the numbers $a_1, a_N, a_{N+1}, a_{N+2}, \ldots$ , then we of course have $v_p(a_{n+1}) = v_p(a_n)$ for all $n \ge N$ . For the rest of the primes, which we have finitely many, we must have $v_p(a_{n+1}) = v_p(a_n)$ for all large enough $n$ . But this means that the sequence $a_n$ is constant, which is a contradiction. Thus, the statement of the lemma is true.

Now, take any prime $p$ satisfying the condition of lemma 1. Define $v_p(a_n) = b_n$ for all $n$ . We aren't that interested in the cases where $b_{n+1} = b_n$ , but luckily we have infinitely many interesting cases.

Lemma 2. If $b_{n+1} > b_n$ , we have $b_{n+1} = b_1$ .

Proof: we divide into two cases, one where $b_{n+1} > b_1$ , and one where $b_{n+1} < b_1$ . We prove that both of these cases lead into a contradiction, which proves the lemma.

If $b_{n+1} > b_1$ , then $v_p(a_{n+1}^2 - a_na_{n+1} + a_na_1) = v_p(a_na_1) = b_n + b_1 < b_{n+1} + b_1 = v_p(a_{n+1}a_1)$ , contradicting the fact that $a_{n+1}a_1$ divides $a_{n+1}^2 - a_na_{n+1} + a_na_1$ .
In a similar manner we see that if $b_{n+1} < b_1$ , then the $v_p$ of the denominator is $b_n + b_{n+1}$ , which is less than $b_{n+1} + b_1$ , since $b_1 > b_{n+1} > b_n$ . Thus, we must have $b_{n+1} = b_1$ .

Lemma 3. If $b_{n+1} < b_n$ , then we have $b_1 \ge b_{n+1}$ .

Proof. Again, a proof by contradiction. Now, the $v_p$ of the denominator is $2b_{n+1}$ , which is less than $b_1 + b_{n+1}$ .

Now, we have our setup ready. We only need the following crucial lemma, and then we are basically done:

Lemma 4. There exists an $n \ge N$ such that $b_n = b_1$ .

Proof. Surprise, a proof by contradiction. Now, if $b_{n+1} > b_n$ for some $n$ , then $b_{n+1} = b_1$ due to lemma 2. This can't happen, so $b_{n+1} \le b_n$ for all $n$ . So $b_n$ is a decreasing sequence, which is a contradiction with the fact that $b_{n+1} \neq b_n$ for infinitely many $n$ , and that $b_n \ge 0$ for all $n$ .

Now, take such $n$ that $b_n = b_1$ . If $b_{n+1} = b_n$ , just increment $n$ by $1$ as long as we have $b_{n+1} \neq b_n = b_1$ . This gives a contradiction:

if $b_{n+1} > b_n$ , then due to lemma 2 we have $b_1 = b_{n+1} > b_n = b_1$ , a contradiction.

if $b_{n+1} < b_n$ , then due to lemma 3 we have $b_1 \le b_{n+1} < b_n = b_1$ , a contradiction.

Thus, the original assumption of the statement being false gave a contradiction. The sequence $a_m$ is therefore constant starting from some point.

Motivation:

The divisibility condition given is very nice for investigating the $p$ -adic valuations, as there are no constant terms. Then, you just bash the cases a little bit to use the well-known lemma $v_p(a \pm b) = \min(v_p(a), v_p(b))$ for $v_p(a) \neq v_p(b)$ . I was hoping for a direct contradiction in either one of the cases $b_{n+1} > b_n$ or $b_{n+1} < b_n$ , but I wasn't able do get this, so I just picked up all the nice information I got from the case-work there. When you really look at lemmas 2 and 3, it's not too difficult to come up with the rest of the solution. Lemma 1 is only needed to describe the prime we pick for our " $v_p$ -bash".

This post has been edited 2 times. Last edited by Loppukilpailija, Jul 17, 2018, 4:05 PM
Reason: Add motivation.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

62861

3564 posts

62861

#12 h Jul 10, 2018, 5:42 PM • 12 Y

Y by Loppukilpailija, nmd27082001, pavel kozlov, Reef334, XbenX, edfearay123, centslordm, leozitz, Wizard0001, Adventure10, Mango247, buddyram

The difference $\frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ is also an integer for $n \ge N$ .
Hence
$a_1 a_{n+1} \mid a_{n+1}^2 - a_n a_{n+1} + a_1 a_n \equiv (a_{n+1} - a_1)(a_{n+1} - a_n).$
Lemma. If $a$ , $x$ , $y$ are positive integers with $ay \mid (y - a)(y - x)$ and $p$ is a prime, then
$\min\big(\nu_p(a), \nu_p(x)\big) \le \nu_p(y) \le \max\big(\nu_p(a), \nu_p(x)\big).$ This can be easily proved by examining the possibilities $\nu_p(y) < \min\big(\nu_p(a), \nu_p(x)\big)$ and $\nu_p(y) > \max\big(\nu_p(a), \nu_p(x)\big)$ ; both lead to $\nu_p$ contradictions in the divisibility.

Corollary 1. $\gcd(a_1, a_n) \mid a_{n+1} \mid \mathrm{lcm}(a_1, a_n)$ for $n \ge N$ .

Corollary 2. $\gcd(a_1, a_n) \mid \gcd(a_1, a_{n+1})$ and $\mathrm{lcm}(a_1, a_{n+1}) \mid \mathrm{lcm}(a_1, a_n)$ for $n \ge N$ .

Hence $\{\gcd(a_1, a_n)\}_{n \ge N}$ and $\{\mathrm{lcm}(a_1, a_n)\}_{n \ge N}$ are increasing and decreasing sequences (respectively) bounded by $a_1$ . Thus they are eventually constant; say $\gcd(a_1, a_m) = u$ and $\mathrm{lcm}(a_1, a_m) = v$ for $m \ge M$ . Then
$a_m = \frac{\gcd(a_1, a_m) \cdot \mathrm{lcm}(a_1, a_m)}{a_1} = \frac{uv}{a_1}$ for all $m \ge M$ , as desired.

This post has been edited 1 time. Last edited by 62861, Jul 10, 2018, 5:45 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yugrey

2326 posts

yugrey

#13 h Jul 10, 2018, 7:27 PM • 3 Y

Y by Adventure10, Mango247, buddyram

v_Enhance wrote:

The condition implies that the difference $\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.

Claim: If $p \nmid a_1$ , then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ for $n \ge N$ .

Proof. The third term in the difference must have nonnegative $\nu_p$ . $\blacksquare$

Claim: If $p \mid a_1$ , then $\nu_p(a_n)$ is eventually constant.

Proof. By hypothesis $\nu_p(a_1) > 0$ . We consider two cases,

First assume $\nu_p(a_k) \ge \nu_p(a_1)$ for some $k > N$ . We claim that for any $n \ge k$ (by induction) we have: $\nu_p(a_1) \le \nu_p(a_{n+1}) \le \nu_p(a_n).$ Note in this case that $\nu(\frac{a_n}{a_1}) \ge 0$ , so we must 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 of the summands 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 summands two must have equal $p$ -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, eventually $\nu_p(a_{n+1}) \ge \nu_p(a_n)$ in either possible situation, but $\nu_p(a_n)$ is bounded above by $\nu_p(a_1) - 1$ , so in this case we must also stabilize. \qedhere

$\blacksquare$

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

Remark: 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.

This is basically my solution. This "caveat" at the end is easy to get around if you notice that since $\frac{a_{n+1}^2-a_na_{n+1}+a_na_1}{a_1a_{n+1}}$ is an integer, $a_{n+1} \mid a_na_1$ , so eventually $\frac{a_n}{(a_n,a_1)}$ converges to a constant. Then you basically do this analysis only on primes that divide $a_1$ , of which there are finitely many. I think this is the more intuitive way to deal with it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

suli

1498 posts

suli

#14 h Jul 10, 2018, 8:17 PM • 3 Y

Y by Adventure10, Mango247, buddyram

For any prime $p$ , $v_p (a_{n+1})$ is between $v_p (a_n)$ and $v_p (a_1)$ . That's it. Was expecting more from an IMO P5

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JuanOrtiz

366 posts

JuanOrtiz

#15 h Jul 10, 2018, 9:19 PM • 2 Y

Y by Adventure10, Mango247

Let $x=a_1$ . Throughout the problem, $n$ will denote an arbitrary number $\ge N$ . Notice
$\frac{a_{n}}{a_{n+1}} + \frac{a_{n+1}-a_n}{x} = \left( \frac{a_1}{a_2}+\cdots + \frac{a_n}{a_{n+1}} + \frac{a_{n+1}}{x} \right) -\left( \frac{a_1}{a_2}+\cdots + \frac{a_n}{x} \right)$ is an integer. Thus $a_{n+1}=\frac{a_nx}{\ell_n}$ for some positive integer $\ell_n$ such that $x| \ell_n+a_{n+1}-a_n$ . Thus, for any prime $p\nmid x$ , we have $v_p(a_n)$ is decreasing, and so eventually becomes constant. There's finitely many primes that divide $a_N$ , and so there's some $M\ge N$ such that for any $p\nmid x$ , the quantity $v_p(a_n)$ is fixed after $n\ge M$ , and the $\ell_n$ 's are only divisible by primes in $P:=\{ p | x\}$ , i.e. primes that divide $x$ . From now on, $n$ will denote an arbitrary number $\ge M$ .

Let $p\in P$ and set $b:= v_p(x)$ , $b_n := v_p(a_n)$ . Assume for some $n$ , $b_{n+1}> b_n$ , so that $b > v_p(\ell_n)$ . Notice $v_p(a_{n+1}-a_n) = b_n$ but $b\le v_p(\ell_n+a_{n+1}-a_n)$ , and so $b_n=v_p(\ell_n) < b$ . Thus $b_{n+1}=b$ and so $p^b | \ell_{n+1} + a_{n+2}$ . But $v_p(\ell_{n+1}) + v_p(a_{n+2}) = 2b$ and so both must be $b$ , thus $b_{n+2}=b$ and thus the sequence $\{b_i\}$ is eventually constant. Otherwise, the sequence is never increasing, but it can never be negative, so it's also eventually constant.

Since $P$ is finite, and all these sequences are constant, we get the $P$ -part of the $\{a_n\}$ sequence is eventually constant. But the first paragraph proves the non- $P$ part is also eventually constant. Thus, the sequence itself is eventually constant as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Taha1381

816 posts

Taha1381

#16 h Jul 11, 2018, 3:58 AM • 2 Y

Y by Adventure10, buddyram

The proof is quite straight for a problem $5$ .

Lemma:There are finite primes dividing one or more elements of the sequence.

Proof:Assume for country then there exists a prime $p$ so that $p$ divides $a_{t+1}$ for some large $t$ but not the previous elements of the subset.Since
$\frac{a_{t+1}}{a_1} - \frac{a_t}{a_1} + \frac{a_t}{a_{t+1}}$ has to be an integer this is impossible.

Let $\mathbb{P}$ denote the set of primes dividing at least one element of the sequence and take $p \in \mathbb{P}$ .We divide the problem into two cases.

First case: $v_p(a_n) <v_p(a_1)$ holds for all integer $n \ge N$ :Since $\frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ has to be an integer using nothing more than $p$ -adic calculations one can show $v_p(a_N) \le v_p(a_{N+!} \le \dots$ because the sequence of $v_p(a_i)$ has an upper bound it has to be constant after somewhere.

Second case :There exist $\ell \ge N$ so that $v_p(a_{\ell }) \ge v_p(a_1)$ .By induction and some $p$ -adic calculations one can prove $v_p(a_{\ell }) \ge v_p(a_{\ell +1}) \ge \dots$ and all this values are bigger than or equal to $v_p(a_1)$ so by FMID it has to be constant after somewhere.

So there exist an $M$ so that powers of all primes in $\mathbb{P}$ is constant in $a_M,a_{M+1},\dots$ since they are the only primes dividing one or more element of the sequence hence all these numbers have to be equal.

Is this solution true?If so then why is this a problem $5$ (I came up with it within 30 minutes in the mock imo we had in Iran while I spend some hours or days to solve some other problems 5's).

Remark:I noticed this is a way to deal with the issue evan remarked in his answer to show the wrong appropach..

This post has been edited 3 times. Last edited by Taha1381, Jul 11, 2018, 1:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

reality95

12 posts

reality95

#17 h Jul 11, 2018, 8:25 PM • 4 Y

Y by rmtf1111, Adventure10, Mango247, buddyram

More or less the same idea as above.
Suppose that $n \ge N$ and $a_1 = c$ then we get that $ca_{n + 1} | a_{n+1}^2 + a_nc - a_na_{n+1}$
We must have for every prime $p$ $v_p(c) + v_p(a_{n + 1}) \le v_p(a_{n+1}^2 + a_nc - a_na_{n+1})$ .

$\textbf{Lemma 1.}$ $v_p(a_{n + 1}) \le \max(v_p(c),v_p(a_n))$

Proof: Suppose the contrary, then $v_p(c) + v_p(a_n) < v_p(a_n) + v_p(a_{n + 1}) < 2v_p(a_{n + 1})$ so $v_p(c) + v_p(a_{n + 1}) \le v_p(c) + v_p(a_n)$ or $v_p(a_{n + 1}) \le v_p(a_n)$ , contradiction.

$\textbf{Lemma 2.}$ If $v_p(a_{n + 1}) < v_p(a_n)$ then $v_p(a_{n + 1}) \ge v_p(c)$

Proof: Suppose $v_p(a_{n + 1}) < v_p(c) \le v_p(a_n)$ then $2v_p(a_{n + 1}) < v_p(a_{n + 1}) + v_p(a_n) < v_p(c) + v_p(a_n)$ so $v_p(c) + v_p(a_n) \le 2v_p(a_{n + 1})$ , contradiction.

By lemma $1$ it's also possible to prove that there are finite number of prime $p$ such that $p$ divides at least one $a_n$ .

Now consider the following cases:

$\textbf{Case 1.}$ $v_p(a_N) < v_p(c)$ .

We must have that $v_p(a_n) \le v_p(c)$ from lemma $1$ and induction.

Suppose there exists $n$ with $v_p(a_{n + 1}) < v_p(a_n)$ , then $v_p(a_n) > v_p(a_{n + 1}) \ge v_p(c)$ , contradiction.

Therefore, sequence $b_{n} = v_p(a_{n + N})$ is upper bounded and increasing, so it converges.

$\textbf{Case 2.}$ $v_p(a_N) \ge v_p(c)$ , then one can prove by induction with lemma $2$ that $v_p(a_n) \ge v_p(c)$ .

Suppose there exist $n$ with $v_p(a_{n + 1}) > v_p(a_n)$ , then $v_p(a_n) \ge \max(v_p(c),v_p(a_n)) > v_p(a_{n + 1}) > v_p(a_n)$ , contradiction.

Therefore, sequence $c_{n} = v_p(a_{n + N})$ is lower bounded and decreasing, so it converges.

There are finite prime numbers $p$ so the conclusion follows.

This post has been edited 3 times. Last edited by reality95, Jul 11, 2018, 8:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orthocentre

72 posts

orthocentre

#18 h Jul 13, 2018, 9:36 AM • 2 Y

Y by Adventure10, buddyram

What is $p$ -adic valuation?

This post has been edited 1 time. Last edited by orthocentre, Apr 7, 2019, 9:49 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ChetanPosani

41 posts

ChetanPosani

#72 h Dec 19, 2023, 5:46 AM • 1 Y

Y by buddyram

nice problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

792 posts

shendrew7

#73 h Dec 20, 2023, 5:29 PM • 1 Y

Y by buddyram

Denote the given sum as $S_n$ . For $n \ge N$ , we are given that
$S_{n+1}-S_n = \frac{a_{n+1}-a_n}{a_1}+\frac{a_n}{a_{n+1}}$
is an integer. Consider the following cases for $v_p(a_n)$ and $v_p(a_{n+1})$ , where $p$ is an arbitrary prime:

$v_p(a_n) > v_p(a_{n+1}): \quad$ We get $v_p\left(\frac{a_n}{a_{n+1}}\right) > 0$ , so we just need
$v_p\left(\frac{a_{n+1}-a_n}{a_1}\right) \ge 0 \implies v_p(a_{n+1}) \ge v_p(a_1).$
$v_p(a_n) < v_p(a_{n+1}): \quad$ Since $v_p\left(\frac{a_n}{a_{n+1}}\right) < 0$ , we must have
$v_p\left(\frac{a_n}{a_{n+1}}\right) = v_p\left(\frac{a_{n+1}-a_n}{a_1}\right) \implies v_p(a_{n+1}) = v_p(a_1).$
$v_p(a_n) = v_p(a_{n+1}): \quad$ No definite outcome.

Thus the behavior of our sequence $v_p(a_{N+1}), v_p(a_{N+2}), v_p(a_{N+3}), \ldots$ can be modeled as follows:

This sequence begins greater than or equal to $v_p(a_1)$ and is weakly decreasing, but is bounded by $v_p(a_1)$ .
This sequence begins less than $v_p(a_1)$ and will remain constant until, at some point, it leaps to $v_p(a_1)$ , where it forever remains fixed.

As $a_1$ has finitely many prime factors, and our sequence is monotonic and eventually remains constant for all $p$ , we get the desired conclusion. $\blacksquare$

This post has been edited 1 time. Last edited by shendrew7, Dec 20, 2023, 5:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

174 posts

lelouchvigeo

#74 h Jan 25, 2024, 5:54 PM • 1 Y

Y by buddyram

We have $a_1a_{N+1}$ $\mid$ $a_{N+1} ( a_{N+1} - a_N) +$ $a_{1}a_N$
Claim : $v_p(a_{N+1}) \leq v_p(a_N)$
FTSOC, lets assume $v_p(a_{N+1}) > v_p(a_N)$
Therefore $v_p(a_1) + v_p(a_{N+1}) \leq$ $Min[ v_p(a_{N+1}) +v_p(a_N) , v_p(a_1) + v_p(a_N)]$
Since $v_p(a_1) + v_p(a_N)$ is always less than $v_p(a_1) + v_p(a_{N+1})$ . We get our contradiction.
Now it is easy to see we will get a constant sequence after some time

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dkedu

180 posts

dkedu

#75 h Jan 27, 2024, 9:42 PM • 1 Y

Y by buddyram

Note that $\frac{a_{n+1}-a_n}{a_1}+ \frac{a_n}{a_{n+1}}$ must be an integer for all $n > N$ .

Claim: $\nu_p(a_i)$ is eventually constant and bounded by $\nu_p(a_1)$ .

We will do casework.
Case 1: $\nu_p(a_n) < \nu_p(a_{n+1})$
We get that $\nu_p\left(\frac{a_{n+1}-a_n}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right)$ so $\nu_p(a_{n+1}) = \nu_p(a_1)$ .

Case 2: $\nu_p(a_n) > \nu_p(a_{n+1})$
We get that $\nu_p\left(\frac{a_{n+1}-a_n}{a_1}\right) \ge 0$ so $\nu_p(a_{n+1}) \ge \nu_p(a_1)$ .

From these two cases we can conclude the claim. Now we are done since the claim implies the sequence is eventually constant.

This post has been edited 1 time. Last edited by dkedu, Jan 27, 2024, 9:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Martin.s

1532 posts

Martin.s

#76 h Mar 3, 2024, 9:00 AM • 1 Y

Y by buddyram

First of all, it $n=2$ is not possible since we must have $a_{2^m} + 2a_{2^{m+1}} = 0$ for each $m$ which inductively gives $a_1 = (-2)^ma_{2^m},$ which means that $2^m|a_1$ for every $m$ — this is impossible since $a_1$ must be non-zero.

We will show that it applies to each $n \geq 3.$ It is enough for each $n$ to find a function $f_n : \mathbb{N} \to \mathbb{N},$ which from now on I will denote with $f,$ with the properties
(a) $f(rs) = f(r)f(s)$ for each $r,s \in \mathbb{N}$
(b) $f(1) + 2f(2) + \cdots + nf(n) = 0$ .

Indeed, if $f$ satisfies (a) and (b), then setting $a_m = f(m)$ for each $m$ , we have $\displaystyle{a_k + 2a_{2k} + \cdots + na_{nk} = f(k) + 2f(2k) + \cdots + nf(nk) = f(k)(1 + 2f(2) + \cdots +nf(n)) = 0.}$

We can therefore consider $n \geq 3.$

We know from Bertrand's theorem that for every $n \geq 2,$ there exists a prime $p$ with $n/2 < p \leq n.$ Let $p$ be the greatest prime less than or equal to $q$ and $n,$ where $q$ is the largest prime that is less than $n.$ Then we have $n/4 < q < p \leq n.$

If $f(m) = a^{m_p}b^{m_q},$ posit where $m_p, m_q$ are their powers in the prime factorization, and $a, b$ are nonzero integers which will be determined later. We see that (a) is satisfied, and it is enough to choose them appropriately $a, b$ so that (b) is also satisfied.

Case 1: $q > n/2.$ Then we want $n-2 + pf(p) + qf(q) = 0.$ Because $p, q$ are coprime, there are $x, y$ such $px + qy = 1.$ We define $a = -(n-2)x, b = -(n-2)y,$ and we are done.

Case 2: $n/3 < q \leq n/2.$ Then we want $n-3 + pf(p) + qf(q) + 2qf(2q) = 0.$

Case 2a: If $q=2,$ then it must be $n=3$ or $n=4$ (since if $n \geq 5,$ then $p \geq 5$ and $q \geq 3$ ). The case $n=3$ is rejected after $q > n/2.$ For $n=4,$ we have $p=3, q=2,$ and want $1 + 3f(3) + 2f(2) + 4f(2)^2 = 0,$ and it is enough to choose $a = f(3) = -1$ and $b = f(2) = -1.$

Case 2b: If $q > 2,$ then we want $n-3 + pf(p) + 3qf(q) = 0,$ and because $p, 3q$ are coprime, we can find suitable $a, b$ as in case 1. (For the $a, b$ non-zeros to be, it is enough to check that $n-3 \neq 0,$ which is true since if $n=3,$ we would have $q=2$ and would not be in case 2.)

Case 3: $n/4 < q \leq n/3.$ Then we want $n-4 + pf(p) + qf(q) + 2qf(2q) + 3qf(3q) = 0.$

Case 3a: If $q \leq 3,$ then you must $n \leq 6.$ (Since if $n \geq 7,$ then $p \geq 7$ and $q \geq 5 > 3.$ ) But if $n \leq 6,$ then $q \leq n/3 \leq 2.$ So $q = 2,$ and $n=6.$ But this is inappropriate since for $n=6,$ we have $q=3.$ So here we have nothing to control.

Case 3b: If $q > 3,$ then we want $n-4 + pf(p) + 6qf(q) = 0,$ and because $p, 6q$ are coprime, we can find suitable $a, b$ as in case 1. (For the $a, b$ non-zeros to be, it is enough to check that $n \neq 4,$ which is true since if $n=4,$ we would have $q=2$ and would not be in case 3.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Markas

105 posts

Markas

#77 h May 5, 2024, 2:00 PM

Y by

From the condition we get that $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$ . Now if $p \not \mid a_1$ , then the first two terms of $S(n)$ have $\nu_p \geq 0$ $\Rightarrow$ $\nu_p(\frac{a_n}{a_{n+1}}) \geq 0$ $\Rightarrow$ $\nu_p(a_n) \geq \nu_p(a_{n+1})$ for $n \geq N$ . Now we will prove that if $p \mid a_1$ , then $\nu_p(a_n)$ will be constant at some point. We have that $\nu_p(a_1) > 0$ . Let $\nu_p(a_k) \ge \nu_p(a_1)$ for $k > N$ . We will show that for all $n \ge k$ we have $\nu_p(a_1) \leq \nu_p(a_{n+1}) \leq \nu_p(a_n)$ , which can be done by induction on n. Now from $\nu(\frac{a_n}{a_1}) \geq 0$ , we have that $\nu_p(\frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}}) \geq 0$ which gives us the inequality we wanted, if thats not true we will have exactly one term of $S(n)$ with $\nu_p \geq 0$ $\Rightarrow$ $\nu_p(a_n)$ is monotonic and at the same time is lower bounded by $\nu_p(a_1)$ $\Rightarrow$ it will eventually be constant.
Now let $\nu_p(a_k) < \nu_p(a_1)$ for every $k > N$ . Also get any $n > N$ . We have $\nu_p(\frac{a_{n+1}}{a_1}) < 0$ , and also $\nu_p(\frac{a_n}{a_1}) < 0$ , so from the three terms of $S(n)$ , two must have equal $\nu_p$ 's. We will check all 3 cases. 1) $\nu_p(\frac{a_{n+1}}{a_1}) = \nu_p(\frac{a_n}{a_1})$ $\Rightarrow$ ${\nu_p(a_{n+1}) = \nu_p(a_{n})}$ , which is enough. 2) $\nu_p(\frac{a_{n+1}}{a_1}) = \nu_p(\frac{a_n}{a_{n+1}})$ $\Rightarrow$ ${\nu_p(a_{n+1}) = \frac{\nu_p(a_n) + \nu_p(a_1)}{2}}$ , which is also enough. 3) $\nu_p(\frac{a_{n}}{a_1}) = \nu_p(\frac{a_n}{a_{n+1}})$ $\Rightarrow$ $\nu_p(a_{n+1}) = \nu_p(a_1)$ , but this is false $\Rightarrow$ $\nu_p(a_{n+1}) \ge \nu_p(a_n)$ and $\nu_p(a_n)$ is upper bounded by $\nu_p(a_1)$ , so we will get to a constant eventually. Since we apply this to finitely many primes, at some point $\nu_p(a_n)$ will get fixed for all $p \mid a_1$ $\Rightarrow$ the sequence will satisfy $a_{n+1} \mid a_n$ for all n $\Rightarrow$ it will eventually be constant.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathandski

727 posts

Mathandski

#78 h Aug 27, 2024, 7:45 PM

Y by

My solution was incorrect. Thanks for report!

This post has been edited 1 time. Last edited by Mathandski, Jan 13, 2025, 6:25 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathLuis

1471 posts

MathLuis

#79 h Sep 12, 2024, 9:11 PM

Y by

Let the whole sum be $S_n$ then for $n \ge N$ we will consider $S_{n+1}-S_n$ , so we have that:
$S_{n+1}-S_n \in \mathbb Z \implies \frac{a_{n+1}}{a_1}+\frac{a_n}{a_{n+1}}-\frac{a_n}{a_1}=\frac{a_{n+1}-a_n}{a_1}+\frac{a_n}{a_{n+1}}=\frac{a_{n+1}^2-a_na_{n+1}+a_na_1}{a_1a_{n+1}} \in \mathbb Z$ Therefore $a_1a_{n+1} \mid a_{n+1}^2-a_na_{n+1}+a_na_1$ so $a_{n+1} \mid a_na_1$
Now if $p \not \; \mid a_1$ then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ so it becomes a decreasing sequence so it will be eventually constant.
Now notice that if we had for some $p$ prime that $p \mid a_1,a_n$ then $p \mid a_{n+1}$ so we can let $a_i=p \cdot b_i$ and realice we have the same condition for the new sequence, therefore by repeating until stuck we have that $\gcd(a_1,a_n) \mid a_{n+1}$ and from here we can also easly get $a_{n+1} \mid \text{lcm}(a_1,a_n)$ , so now for a prime $p \mid a_1$ we have that $\text{min} \{\nu_p(a_1), \nu_p(a_n) \} \le \nu_p(a_{n+1}) \le \text{max} \{\nu_p(a_1), \nu_p(a_n) \}$
This holds for all $n \ge N$ so if we ever had $\nu_p(a_n)=\nu_p(a_1)$ then we would get $\nu_p(a_j)=\nu_p(a_1)$ for all $j \ge n$
And in the other 2 cases we get that either both $\nu_p(a_n), \nu_p(a_{n+1})$ are less than $\nu_p(a_1)$ or we get that $\nu_p(a_n) \ge \nu_p(a_{n+1})$ so either way for any such $p$ we get that the sequence of $\nu_p$ 's stabilizes and converges at some point.
Therefore for some $M$ we have that $a_n$ is constant for all $n \ge M$ (since then we would get that $a_{n+1} \mid a_n$ and so on, so we would mess with decreasing-ness) thus we are done.

This post has been edited 2 times. Last edited by MathLuis, Sep 12, 2024, 9:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

numbertheory97

39 posts

numbertheory97

#80 h Sep 24, 2024, 12:25 AM

Y by

We prove the following quick claim, which allows us to focus on a finite number of primes.

Claim: Only finitely many primes divide $a_1, a_2, \dots$ .

Proof. Actually, the only primes that divide elements of the sequence are the divisors of $a_1, a_2, \dots, a_{N - 1}$ . Suppose $p \nmid a_1a_2 \cdots a_{N - 1}$ and $p \mid a_M$ for some $M \geq N$ . Then $\nu_p\left(\frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots + \frac{a_{M - 1}}{a_M} + \frac{a_M}{a_1}\right) = \nu_p\left(\frac{a_{M - 1}}{a_M}\right) < 0$ since $\nu_p(a_M) > 0$ , a contradiction since the expression is parentheses is an integer. Since finitely many primes are divisors of $a_1a_2 \dots a_{N - 1}$ , we're done. $\square$

Now let $p$ one of these primes; it suffices to show that the sequence $\nu_p(a_1), \nu_p(a_2), \dots$ is eventually constant.

Claim: For any integer $n \geq N$ , we have $\nu_p(a_1) \leq \nu_p(a_n) \leq \nu_p(a_N)$ if $\nu_p(a_1) \leq \nu_p(a_N)$ and $\nu_p(a_N) \leq \nu_p(a_n) \leq \nu_p(a_1)$ otherwise.

Proof. Observe that
$\begin{align*} \left(\frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots + \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) - \left(\frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots + \frac{a_{n - 1}}{a_n} + \frac{a_n}{a_1}\right) \\ = \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} - \frac{a_n}{a_1} \end{align*}$ is an integer, so $a_n/a_{n + 1} + a_{n + 1}/a_1$ and $a_n/a_1$ have the same denominator. Thus $\nu_p\left(\frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) \geq 0 \iff \nu_p\left(\frac{a_n}{a_1}\right) \geq 0$ and $\nu_p\left(\frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) < 0 \iff \nu_p\left(\frac{a_n}{a_1}\right) < 0 \iff \nu_p\left(\frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_1}\right) < 0.$
Let $k = \nu_p(a_n/a_{n + 1} + a_{n + 1}/a_1)$ . Suppose first that $\nu_p(a_n/a_1) \geq 0$ , or alternately $\nu_p(a_n) \geq \nu_p(a_1)$ . This implies that $k \geq 0$ as well, so if $\nu_p(a_{n + 1}) > \nu_p(a_n)$ or $\nu_p(a_{n + 1}) < \nu_p(a_1)$ we get $k < 0$ , a contradiction. Thus $\nu_p(a_1) \leq \nu_p(a_{n + 1}) \leq \nu_p(a_n)$ .

On the other hand, suppose $\nu_p(a_n) < \nu_p(a_1)$ . Then $k = \nu_p(a_n/a_1) = \nu_p(a_n) - \nu_p(a_1)$ , but $k = \min\left(\nu_p\left(\frac{a_n}{a_{n + 1}}\right), \nu_p\left(\frac{a_{n + 1}}{a_1}\right)\right)$ unless $\nu_p(a_n/a_{n + 1}) = \nu_p(a_{n + 1}/a_1)$ , which is clearly impossible since this implies $k = \frac12(\nu_p(a_n) - \nu_p(a_1))$ . Thus $\nu_p(a_{n + 1}) \in \{\nu_p(a_1), \nu_p(a_n)\}$ .

In either case, by starting at $n = N$ and inducting upward, we obtain the desired bounds on $\nu_p(a_n)$ . $\square$

The claim implies that for $n \geq N$ , the sequence $\nu_p(a_n)$ is monotonic and bounded between $\nu_p(a_1)$ and $\nu_p(a_n)$ , so it clearly has a limiting value. Since we're only examining finitely many primes, there is some integer $K$ for which $\nu_p(a_K) = \nu_p(a_{K + 1}) = \dots$ , and thus the sequence is constant beginning with $a_K$ . This completes the proof. $\square$

Remark. I would have lost partial credit if I had actually done this problem in contest, since it didn't occur to me until reading hints after solving that simply showing $\nu_p(a_n)$ converges for each prime doesn't quite finish.

This post has been edited 1 time. Last edited by numbertheory97, Sep 24, 2024, 12:27 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3441 posts

ihatemath123

#82 h Nov 27, 2024, 9:49 PM

Y by

Claim: There are finitely many primes that divide an integer in the sequence.
Proof: For $i \geq N$ and for any prime $p$ , the integer condition implies that
$\nu_p \left( \tfrac{a_{i-1}}{a_i} \right) \geq \min \left(\nu_p \left( \tfrac{a_1}{a_2} \right), \nu_p \left( \tfrac{a_2}{a_3} \right), \ldots, \nu_p \left( \tfrac{a_{i-2}}{a_{i-1}} \right), \nu_p \left( \tfrac{a_{i}}{a_{1}} \right) \right).$ In particular, if we set $p$ to a prime that does not divide any of $a_1, \dots, a_{i-1}$ , it follows that $a_N, a_{N+1}, \dots$ cannot contain new prime divisors that don't divide any of $a_1, \dots, a_{N-1}$ .

From hereon, let $i$ be any integer index greater than $N$ and fix some arbitrary prime $p$ .

Claim: If $\nu ( a_{i-1} )\geq \nu ( a_1 )$ , it follows that $\nu ( a_i ) \geq \nu ( a_1 )$ .
Proof: Suppose FTSOC that $\nu ( a_i )< \nu ( a_1 )$ . Subtracting the assertion for $i-1$ from $i$ implies that $- \tfrac{a_{i-1}}{a_1} + \tfrac{a_{i-1}}{a_i} + \tfrac{a_i}{a_1}$ is an integer. But by assumption, $\nu ( \tfrac{a_{i-1}}{a_1} )$ and $\nu ( \tfrac{a_{i-1}}{a_i} )$ are positive while $\nu ( \tfrac{a_i}{a_1} )$ is negative. This is a contradiction.

Claim: If $\nu (a_{i-1} ) < \nu ( a_i )$ , we have $\nu (a_i) = \nu (a_1)$ .
Proof: Once again, we only use that $- \tfrac{a_{i-1}}{a_1} + \tfrac{a_{i-1}}{a_i} + \tfrac{a_i}{a_1}$ is an integer. By assumption, $\nu (\tfrac{a_{i-1}}{a_i})$ is negative – moreover, by assumption, $\nu ( \tfrac{a_{i-1}}{a_1} )$ and $\nu ( \tfrac{a_i}{a_1} )$ are not equal. Therefore, to satisfy the integer condition, the smaller of the two, $\nu ( \tfrac{a_{i-1}}{a_1} )$ , must equal $\nu (\tfrac{a_{i-1}}{a_i})$ . This implies the claim.

If $\nu_p (a_{i-1} ) < \nu_p ( a_i )$ for some $i$ , due to the first and second claims combined, $\nu_p (a_k) = \nu_p (a_1)$ for all $k \geq i$ . Otherwise, we're already done. Applying this on our finite set of primes finishes the problem.

This post has been edited 1 time. Last edited by ihatemath123, Nov 27, 2024, 9:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bjump

994 posts

bjump

#83 h Dec 27, 2024, 3:34 PM

Y by

Note that for integral $C \ge 0$
$\frac{a_1}{a_2} + \frac{a_2}{a_3}+ \cdots +\frac{a_{N+C-1}}{a_{N+C}} + \frac{a_{N+C}}{a_1} \in \mathbb Z$ $\frac{a_1}{a_2} + \frac{a_2}{a_3}+ \cdots +\frac{a_{N+C}}{a_{N+C+1}} + \frac{a_{N+C+1}}{a_1} \in \mathbb Z$ Subtracting the first expression from the second expression gives:
$\frac{a_{N+C+1}}{a_1} + \frac{a_{N+C}}{a_{N+C+1}} -\frac{a_{N+C}}{a_1} \in \mathbb Z$ Suppose for some prime $p$ , $\nu_p (a_1) = 0$ this implies $\nu_p(a_{N+C}) \ge \nu_p(a_{N+C+1})$ implying that the sequence is eventually constant. Now if $\nu_p (a_1) \ge 1$ then if $\nu_p(a_1) >\nu_p (a_{N+C+1}) > \nu_p (a_{N+C})$ We have
$\nu_p (a_{N+C}) - \nu_p (a_{N+C+1}) = \nu_p(a_{N+C+1} - a_{N+C}) -\nu_p (a_1)$ $\nu_p (a_{N+C}) - \nu_p (a_{N+C+1}) = \nu_p(a_{N+C}) -\nu_p (a_1)$ $\nu_p (a_{N+C+1}) = \nu_p (a_1)$ If $\nu_p (a_{N+C})= \nu_p (a_1)$ suppose for the sake of contradiction that $\nu_p (a_{N+C+1}) \neq \nu_p (a_1)$ , we have:
$\nu_p (a_{N+C}) - \nu_p ( a_{N+C+1}) = \nu_p(a_{N+C+1}) - \nu_p (a_1)$ $\nu_p (a_{N+C})+\nu_p (a_1) = 2 \nu_p(a_{N+C+1})$ $\nu_p(a_1) = \nu_p(a_{N+C+1})$ A contradiction.
If $\nu_p(a_1) > \nu_p (a_{N+C}) > \nu_p (a_{N+C+1})$ we have the middle fraction is an integer and it is impossible for $\nu_p(a_{N+C+1} - a_{N+C}) =\nu_p( a_{N+C+1}) \ge \nu_p(a_1)$ to be true.

Now suppose $\nu_p (a_{N+C}) > \nu_p (a_1)$ we have that
$\frac{a_{N+C+1}}{a_1}+\frac{a_{N+C}}{a_{N+C+1}} \in \mathbb Z$ If $\nu_p (a_1) < \nu_p( a_{N+C+1})$ we have $\nu_p(a_{N+C+1} \le \nu_p (a_{N+C})$ . Otherwise $\nu_p (a_{N+C+1}) \le \nu_p (a_i)$ .

Therefore the sequence will be stuck at a constant with $\nu_p$ less than $\nu_p (a_1)$ , $\nu_p(a_1)$ if the sequnce changes at all. It is impossible for the sequence to stay strictly above $\nu_p (a_1)$ due to our last argument. Thus $(a_n)$ is eventually constant.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

174 posts

lelouchvigeo

#84 h Jan 24, 2025, 8:24 AM • 1 Y

Y by alexanderhamilton124

Easy?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihategeo_1969

173 posts

ihategeo_1969

#85 h Feb 14, 2025, 6:52 PM

Y by

No way I still haven't done this.

See that $\frac{a_{n+1}}{a_1}+\frac{a_n}{a_{n+1}}=b_n \iff a_{n+1}a_1b_n-a_na_1=a_{n+1}(a_{n+1}-a_n) \text{ for large }n \left(\clubsuit \right)$ Say a prime $p \mid a_1$ if it exists (or else $a_{n+1} \mid a_n \implies a_{n+1} \leq a_n$ so by discrete IVT we are done).

See that there finitely many such primes $p$ and say $\nu_p(a_1)=C>0$ .

Claim: Either the sequence $(\nu_p(a_n))_{n \geq 1}$ is eventually just $C$ or eventually $\nu_p(a_{n+1}) \leq \nu_p(a_n)$ .
Proof: Say $\nu_p(a_{n+1})>\nu_p(a_n)$ . See that applying $\nu_p$ in $\clubsuit$ we get $\begin{align*} & C+\nu_p(a_{n+1}b_n-a_n)=\nu_p(a_{n+1})+\nu_p(a_{n+1}-a_n) \iff C+\nu_p(a_n)=\nu_p(a_{n+1})+\nu_p(a_n) \iff \nu_p(a_{n+1})=C \end{align*}$ Now see that if $\nu_p(a_{n+2}) \geq \nu_p(a_{n+1})$ then $\nu_p(a_{n+2})=C$ . So assume the contrary. Again applying $\nu_p$ in $\clubsuit$ but rearranged and shifting $n \mapsto n+1$ ; we get $\nu_p(a_{n+2})+C+\nu_p(b_{n+1})=\nu_p(a_{n+2}^2-a_{n+2}a_{n+1}+a_{n+1}a_1)=2\nu_p(a_{n+2}) \implies \nu_p(a_{n+2}) \geq C$ Which is a contradiction. $\square$

This claim obviously finishes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathwiz_1207

93 posts

mathwiz_1207

#86 h Feb 17, 2025, 9:42 PM

Y by

We will prove that the sequence $\{v_p(a_n)\}$ is constant after a finite number of terms. Note that the condition is equivalent to
$\frac{a_{n + 1}}{a_n} + \frac{a_n}{a_{n+1}} - \frac{a_n}{a_1} \in \mathbb{Z} \leftrightarrow \frac{(a_{n+1} - a_n)(a_{n + 1} - a_1)}{a_{n + 1}a_1} \in \mathbb{Z}$ Let $n$ be such that $n \geq N$ in what follows.

If $v_p(a_{n+1}) < v_p(a_n)$ , we must have $v_p(a_{n+1}) \geq v_p(a_1)$ . If $v_p(a_{n + 1}) < v_p(a_1)$ , then
$v_p(a_{n+1} - a_n) + v_p(a_{n + 1} - a_1) - v_p(a_{n+1}) - v_p(a_1) = v_p(a_{n+1}) + v_p(a_{n+1}) - v_p(a_{n+1}) - v_p(a_1) < 0$ a contradiction.

If $v_p(a_{n+1}) > v_p(a_n)$ , we must have $v_p(a_{n + 1}) = v_p(a_1)$ . If $v_p(a_{n + 1} < v_p(a_1)$ , we have
$v_p(a_{n+1} - a_n) + v_p(a_{n + 1} - a_1) - v_p(a_{n+1}) - v_p(a_1) = v_p(a_n) + v_p(a_{n+1}) - v_p(a_{n + 1}) - v_p(a_1) < 0$ a contradiction. Similarly, if $v_p(a_{n+1}) > v_p(a_1)$ , we have
$v_p(a_{n+1} - a_n) + v_p(a_{n + 1} - a_1) - v_p(a_{n+1}) - v_p(a_1) = v_p(a_n) + v_p(a_1) - v_p(a_{n+1}) - v_p(a_1) < 0$ a contradiction.

If $v_p(a_{n + 1}) = v_p(a_n)$ , we must have $v_p(a_{n+1}) \geq v_p(a_1)$ . If $v_p(a_{n+1}) < v_p(a_1)$ , we have
$v_p(a_{n+1}^2 - a_na_{n + 1} + a_1a_n) - v_p(a_{n + 1}) - v_p(a_1) = v_p(a_{n+1}) - v_p(a_1) < 0$ a contradiction.

Now, let $b_n = v_p(a_{n})$ . Then, $b_n \geq b_1$ for all $n \geq N + 1$ , since $b_1 \leq b_{n + 1} < b_n$ , $b_n < b_{n + 1} = b_1$ or $b_1 \leq b_{n + 1} = b_n$ . This implies that after a finite number of terms, either $\{b_n\}$ is $b_1$ or it is constant, so we are done.

This post has been edited 1 time. Last edited by mathwiz_1207, Feb 17, 2025, 9:43 PM
Reason: formatting

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VideoCake

8 posts

VideoCake

#87 h Mar 26, 2025, 8:53 PM

Y by

Solved together with raflikk!

Solution. Denote given expression by $S_n$ , and notice that $S_{n+1} - S_n$ has to be an integer, so
$S_{n+1} - S_n = \frac{a_{n+1} - a_{n}}{a_{1}} - \frac{a_{n}}{a_{n+1}}$ meaning that $a_1a_{n+1} \mid a_{n+1}(a_{n+1} - a_{n}) - a_na_1$ . This implies $a_1 \mid a_{n+1}(a_{n+1} - a_{n})$ and $a_{n+1} \mid a_na_1$ . Suppose that a prime $p$ divides $a_1$ and $a_n$ . Then,
$p \mid a_1 \mid a_{n+1}(a_{n+1} - a_n) \implies p \mid a_{n+1}^2$ which means that $p \mid a_{n+1}$ . Thus, $p \mid a_i$ for all $i \geq n$ . Now we repeat the following step:

Assume that there exists a positive integer $C$ such that all terms $a_i$ with $i \geq C$ are integers, and assume that $a_1$ is an integer. Pick a prime $p$ such that $p \mid a_1$ and $p \mid a_i$ (with $i \geq C$ ). Since all $a_j$ with $j \geq i \geq C$ are integers, we know that $p \mid a_j$ for all $j \geq i$ . Now we divide every term in the sequence by $p$ . All ratios are still the same. (We allow some terms in the sequence to be non-integers after this step). Note how all $a_j$ with $j \geq i$ are still integers, so we pick our new constant $C$ to be equal to $i$ , and note how $a_1$ is still an integer.

Eventually, it is not possible to perform the step by picking a prime $p$ , as $a_1$ only has a finite amount of divisors. Then, $\gcd(a_1, a_i) = 1$ for all $i \geq C$ . Lastly, this means that for every integer $n \geq C$ , we have:
$a_{n+1} \mid a_1a_n \implies a_{n+1} \mid a_n \implies a_{n+1} \leq a_n$ We divided all terms in the sequence with the same primes, so $a_{n+1} \leq a_n$ also holds in the original sequence, so this sequence has to be eventually constant, we are done.

Z K Y