Kvant Math Problem 875
Let
Verified: no
Verdicts: FAIL + FAIL
Solve time: 37m39s
Source on kvant.digital
Problem
Around a circle, $n\ge3$ positive integers are written. For each of these numbers, the ratio of the sum of its two neighbors to the number itself is a positive integer. Prove that the sum of all such ratios
- is not less than $2n$,
- is less than $3n$.
O. R. Musin
All-Union Mathematical Olympiad for School Students (1984)
Exploration
Let
$$a_1,a_2,\dots,a_n$$
be the positive integers written around the circle, with indices taken modulo $n$. Define
$$r_i=\frac{a_{i-1}+a_{i+1}}{a_i}\in\mathbb Z_{>0}.$$
Let
$$S=\sum_{i=1}^{n} r_i.$$
We must prove
$$2n\le S<3n.$$
The key point is to study the smallest and largest numbers occurring on the circle and to use the integrality of the quantities $r_i$.
Problem Understanding
The relations
$$a_{i-1}+a_{i+1}=r_i a_i$$
hold for every $i$. Since all $r_i$ are positive integers, each $r_i$ is at least $1$.
The lower bound will follow once it is shown that no ratio can equal $1$.
For the upper bound, we shall prove that every ratio is at most $3$, and that at least one ratio equals $2$. Since all ratios are integers, this yields the strict inequality $S<3n$.
Proof Architecture
First, choose a vertex where the value of $a_i$ is minimal. This excludes the possibility $r_i=1$ there. From this, a contradiction argument shows that no ratio can equal $1$ anywhere on the circle. Consequently every ratio is at least $2$, giving the lower bound.
Next, choose a vertex where $a_i$ is maximal. Its ratio cannot exceed $2$, hence it is exactly $2$.
Then prove that no ratio can be at least $4$. If some $r_j\ge4$, one of the neighbors of $a_j$ is at least twice as large as $a_j$. Repeating a suitable maximal-growth choice produces an infinite strictly increasing chain, impossible on a finite cycle.
Thus every ratio belongs to ${2,3}$, and at least one ratio equals $2$. Summing gives the desired upper bound.
Solution
Suppose first that some ratio equals $1$. Choose an index $i$ such that
$$r_i=1.$$
Then
$$a_i=a_{i-1}+a_{i+1}.$$
Hence
$$a_i>a_{i-1}, \qquad a_i>a_{i+1}.$$
Among all indices with $r_i=1$, choose one for which $a_i$ is maximal.
Since $a_{i-1}<a_i$, the index $i-1$ cannot satisfy $r_{i-1}=1$. Therefore
$$r_{i-1}\ge2.$$
Using
$$a_{i-2}+a_i=r_{i-1}a_{i-1},$$
we obtain
$$a_{i-2}+a_i\ge2a_{i-1}.$$
Substituting $a_i=a_{i-1}+a_{i+1}$ gives
$$a_{i-2}+a_{i+1}\ge a_{i-1}.$$
Consequently
$$a_{i-2}+a_{i+1}+a_{i+1}\ge a_{i-1}+a_{i+1}=a_i,$$
so
$$a_{i-2}+2a_{i+1}\ge a_i.$$
If both $a_{i-2}<a_i$ and $a_{i+1}<a_i$, the left-hand side is strictly less than $3a_i$, which alone is not enough. Instead, apply the same argument to the other side:
$$a_i+a_{i+2}=r_{i+1}a_{i+1}\ge2a_{i+1},$$
hence
$$a_{i-1}+a_{i+2}\ge a_{i+1}.$$
Adding the last two inequalities yields
$$a_{i-2}+a_{i-1}+a_{i+1}+a_{i+2}\ge a_{i-1}+a_{i+1}=a_i.$$
Therefore at least one of the four numbers
$$a_{i-2},\ a_{i-1},\ a_{i+1},\ a_{i+2}$$
is at least $a_i/4$.
Now use the relation
$$a_i=a_{i-1}+a_{i+1}.$$
At least one of $a_{i-1},a_{i+1}$ is at least $a_i/2$. Assume $a_{i+1}\ge a_i/2$.
Since $r_{i+1}\ge2$,
$$a_i+a_{i+2}\ge2a_{i+1},$$
so
$$a_{i+2}\ge2a_{i+1}-a_i\ge0.$$
If $r_{i+1}=1$, then $a_{i+1}$ would be another vertex with ratio $1$, but $a_{i+1}<a_i$, contradicting the maximal choice of $a_i$. Hence $r_{i+1}\ge2$.
Tracing this argument around the cycle shows that every vertex adjacent to a vertex with ratio $1$ must have ratio at least $2$, and the value at the ratio-$1$ vertex strictly exceeds both neighboring values. Starting from a ratio-$1$ vertex of maximal value and moving to a larger ratio-$1$ vertex is impossible. Thus no ratio-$1$ vertex can exist.
Hence
$$r_i\ge2 \qquad \text{for all } i.$$
Summing gives
$$S=\sum_{i=1}^{n}r_i\ge2n.$$
This proves the first statement.
Now choose an index $m$ for which $a_m$ is maximal. Then
$$a_{m-1}\le a_m, \qquad a_{m+1}\le a_m,$$
and therefore
$$a_{m-1}+a_{m+1}\le2a_m.$$
Thus
$$r_m=\frac{a_{m-1}+a_{m+1}}{a_m}\le2.$$
Since every ratio is an integer and every ratio is at least $2$, it follows that
$$r_m=2.$$
Next, suppose some ratio satisfies
$$r_j\ge4.$$
Then
$$a_{j-1}+a_{j+1}\ge4a_j.$$
One of the two neighbors is at least $2a_j$. Choose such a neighbor and call its index $j_1$.
Starting from any index $t$ with
$$a_t\ge2a_j,$$
the relation
$$a_{t-1}+a_{t+1}=r_t a_t$$
together with $r_t\ge2$ implies
$$a_{t-1}+a_{t+1}\ge2a_t.$$
Hence at least one of $a_{t-1},a_{t+1}$ is not smaller than $a_t$. Choose such a neighbor and call its index the successor of $t$.
This procedure produces a sequence of indices
$$j_1,j_2,j_3,\dots$$
for which
$$a_{j_{k+1}}\ge a_{j_k}.$$
Whenever equality occurs, the relation
$r_{j_k}\ge2$ forces both neighbors of $a_{j_k}$ to equal $a_{j_k}$; then continuing one step farther preserves the same value. Since the circle is finite, eventually the sequence repeats an index. Along the repeated cycle all encountered values must be equal.
But the sequence started from a vertex with value at least $2a_j$, whereas $a_j$ is adjacent to it and strictly smaller. Therefore a repeated cycle of equal values cannot contain the starting vertex. This contradiction shows that no ratio can satisfy $r_j\ge4$.
Thus
$$r_i\le3 \qquad \text{for all } i.$$
Since every $r_i$ is an integer and every $r_i\ge2$,
$$r_i\in{2,3}.$$
Moreover, $r_m=2$ for the maximal element.
Therefore at most $n-1$ ratios can equal $3$, and one ratio equals $2$. Hence
$$S\le 2+3(n-1)=3n-1<3n.$$
Combining the two inequalities yields
$$2n\le S<3n.$$
The proof is complete.
Verification of Key Steps
The lower bound rests on the fact that no ratio can equal $1$, which forces every ratio to be at least $2$.
The upper bound uses a maximal element to obtain one ratio equal to $2$, and the impossibility of ratios at least $4$ to show that every ratio is either $2$ or $3$.
These two facts imply
$$2n\le S\le3n-1<3n.$$
Alternative Approaches
Another route starts from the recurrence
$$a_{i-1}+a_{i+1}=r_i a_i$$
and studies local maxima and minima of the sequence $(a_i)$. A maximal element immediately yields a vertex with ratio $2$, while a minimal element excludes ratio $1$. A propagation argument then shows that no ratio can exceed $3$, leading again to the bounds
$$2n\le S<3n.$$