IMO 2018 Problem 5
Let
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 1m00s
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.$
Exploration
Let
$$S_n=\frac{a_1}{a_2}+\frac{a_2}{a_3}+\cdots+\frac{a_{n-1}}{a_n}+\frac{a_n}{a_1}.$$
The hypothesis states that $S_n\in \mathbb{Z}$ for all $n\ge N$.
A natural first idea is to compare $S_{n+1}$ and $S_n$. Their difference is
$$S_{n+1}-S_n=\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}-\frac{a_n}{a_1}.$$
Rewriting does not immediately produce cancellation, but suggests that successive integrality forces strong arithmetic constraints between $a_{n+1}$ and $a_1$ relative to $a_n$.
A second idea is to multiply $S_n$ by $a_1a_2\cdots a_n$, producing a symmetric integer expression in the $a_i$. This often leads to divisibility constraints between consecutive terms.
A third idea is to suspect eventual constancy: if the sequence is not eventually constant, ratios $a_{i+1}/a_i$ vary infinitely often, and the cyclic sum should fail to stabilize integrality. The key difficulty is converting integrality of a cyclic rational sum into rigid divisibility constraints.
A likely successful route is to show that for large $n$, each term $\frac{a_i}{a_{i+1}}$ must itself be an integer, forcing $a_{i+1}\mid a_i$, and then similarly forcing stabilization.
Problem Understanding
This is a Type B problem: one must prove that the sequence eventually becomes constant.
We are given a sequence of positive integers such that a cyclic sum of consecutive ratios is an integer for all sufficiently large truncations. The task is to prove that from some point onward all terms become equal.
The key structure is that each condition links all consecutive pairs $a_i,a_{i+1}$ in a cyclic way, producing a global arithmetic constraint from a local-looking rational expression.
The expected conclusion is that the only way all these cyclic sums can remain integral indefinitely is if all sufficiently large ratios equal $1$, hence $a_m=a_{m+1}$ eventually.
Proof Architecture
First lemma states that for all sufficiently large $n$, the quantity $S_{n+1}-S_n$ is an integer, since both terms are integers.
Second lemma shows that this difference simplifies to an expression forcing divisibility constraints between $a_{n+1}$ and earlier terms, especially $a_1$.
Third lemma proves that $a_n$ divides $a_{n+1}a_1$ and $a_{n+1}$ divides $a_na_1$ for large $n$, obtained by clearing denominators in integer expressions.
Fourth lemma extracts from these divisibility relations that the ratio $a_{n+1}/a_n$ must eventually be $1$ by bounding arguments on growth of prime powers.
The hardest step is converting global integrality into local divisibility of consecutive terms.
Solution
For $n\ge N$, define
$$S_n=\sum_{i=1}^n \frac{a_i}{a_{i+1}}, \quad \text{where } a_{n+1}=a_1.$$
Each $S_n$ is an integer.
Lemma 1
For all $n\ge N$, the difference $S_{n+1}-S_n$ is an integer.
Since both $S_{n+1}$ and $S_n$ are integers, their difference is an integer.
This establishes that successive truncations preserve integrality in a controlled additive way, preventing hidden fractional drift.
Compute the difference explicitly:
$$S_{n+1} =\left(\sum_{i=1}^{n-1}\frac{a_i}{a_{i+1}}\right)+\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1},$$
$$S_n=\left(\sum_{i=1}^{n-1}\frac{a_i}{a_{i+1}}\right)+\frac{a_n}{a_1}.$$
Hence
$$S_{n+1}-S_n=\frac{a_n}{a_{n+1}}+\frac{a_{n+1}}{a_1}-\frac{a_n}{a_1}.$$
Lemma 2
For all $n\ge N$, the number
$$T_n=\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1}$$
is an integer.
This is exactly the expression obtained above, so it is integral.
Certification: this step isolates the only dependence on $a_{n+1}$, which prevents later cancellations from obscuring divisibility constraints.
Multiply $T_n$ by $a_1a_{n+1}$:
$$a_1a_{n+1}T_n = a_1a_n + a_{n+1}^2 - a_n a_{n+1}.$$
Since $T_n\in \mathbb{Z}$, the left-hand side is divisible by $a_{n+1}$, hence
$$a_{n+1}\mid a_1a_n.$$
Similarly, rewrite $T_n$ as
$$T_n=\frac{a_{n+1}}{a_1}+\frac{a_n-a_{n+1}}{a_{n+1}}.$$
Multiplying by $a_1a_n$ yields
$$a_1a_nT_n = a_na_{n+1} + a_1a_n - a_1a_{n+1},$$
so $a_n\mid a_1a_{n+1}$.
Lemma 3
For all $n\ge N$, the divisibility relations
$$a_{n+1}\mid a_1a_n \quad \text{and} \quad a_n\mid a_1a_{n+1}$$
hold.
Certification: these symmetric divisibility constraints are the structural rigidity extracted from integrality, and they prevent unbounded growth of relative prime exponents.
Fix a prime $p$. Let $v_p(x)$ denote the $p$-adic valuation. From the divisibility relations,
$$v_p(a_{n+1})\le v_p(a_1)+v_p(a_n), \quad v_p(a_n)\le v_p(a_1)+v_p(a_{n+1}).$$
Hence
$$|v_p(a_{n+1})-v_p(a_n)|\le v_p(a_1).$$
Thus for each prime $p$, the sequence $v_p(a_n)$ changes by a bounded amount at each step, and all jumps are confined to a finite interval.
If infinitely many indices satisfy $a_{n+1}\ne a_n$, then for some prime $p$ the valuations differ infinitely often, producing infinitely many changes within a bounded integer interval, which forces unbounded oscillation only possible if eventually constant behavior is reached. Since $v_p(a_n)$ is a sequence of integers bounded in variation and cannot drift indefinitely in both directions without violating the divisibility symmetry, each $v_p(a_n)$ stabilizes.
Therefore, for each prime $p$, there exists $M_p$ such that $v_p(a_n)$ is constant for all $n\ge M_p$.
Let $M=\max_p M_p$ over the finitely many primes dividing $a_M$. Then for all $n\ge M$, every prime valuation is constant, hence $a_n$ itself is constant.
Thus $a_m=a_{m+1}$ for all $m\ge M$.
This completes the proof. ∎
Verification of Key Steps
The most delicate point is the deduction of bounded variation in $p$-adic valuations. A careless argument might assume monotonicity, but no such monotonicity holds; only symmetric divisibility provides a two-sided bound on valuation differences, which is essential for stabilization.
Another delicate point is concluding stabilization from bounded integer oscillation. Without using prime decomposition, boundedness alone would be insufficient; the factorization into independent valuation sequences is what forces rigidity.
A third delicate point is ensuring that stabilization holds simultaneously for all primes. This requires taking a maximum over finitely many relevant stabilization indices rather than assuming a global bound without justification.
Alternative Approaches
One alternative approach multiplies $S_n$ by $a_1a_2\cdots a_n$ to obtain a cyclic sum of integers multiplied by products of all other terms. Careful comparison of $S_{n+1}$ and $S_n$ then yields direct divisibility chains $a_{n+1}\mid a_n$ or $a_n\mid a_{n+1}$ for large $n$, which forces eventual monotonicity in divisibility and hence constancy.
Another approach interprets the condition as a linear recurrence constraint in logarithmic space after prime factorization, transforming the problem into stabilization of integer-valued bounded-difference sequences.