Olympiad Maths Prep

Track / Stage 7 / 300 of 300 #1700 of 2000

Problem 1700

National olympiad second round; IMO P1/P4
Number theory Difficulty 8.0 Prove it

9⋅869 \cdot 86 Write nn natural numbers (n⩾3)(n \geqslant 3) on a circle, such that the ratio of the sum of the two adjacent numbers to the number itself is a natural number for each number, and let the sum of all these ratios be sns_{n}. Prove:
2n⩽sn<3n2 n \leqslant s_{n}<3 n

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

[Proof] Label nn numbers as x1,x2,⋯ ,xnx_{1}, x_{2}, \cdots, x_{n}, then
sn=x1+x3x2+⋯+xn−2+xnxn−1+xn−1+x1xn+xn+x2x1.s_{n}=\frac{x_{1}+x_{3}}{x_{2}}+\cdots+\frac{x_{n-2}+x_{n}}{x_{n-1}}+\frac{x_{n-1}+x_{1}}{x_{n}}+\frac{x_{n}+x_{2}}{x_{1}} .

Thus, sn=(x1x2+x2x1)+(x3x2+x2x3)+⋯+(xn−1xn+xnxn−1)s_{n}=\left(\frac{x_{1}}{x_{2}}+\frac{x_{2}}{x_{1}}\right)+\left(\frac{x_{3}}{x_{2}}+\frac{x_{2}}{x_{3}}\right)+\cdots+\left(\frac{x_{n-1}}{x_{n}}+\frac{x_{n}}{x_{n-1}}\right)
+(xnx1+x1xn)+\left(\frac{x_{n}}{x_{1}}+\frac{x_{1}}{x_{n}}\right)
⩾2n\geqslant 2 n.
We will prove sn<3ns_{n}<3 n by induction.
When n=3n=3, s3=x2+x3x1+x3+x1x2+x1+x2x3s_{3}=\frac{x_{2}+x_{3}}{x_{1}}+\frac{x_{3}+x_{1}}{x_{2}}+\frac{x_{1}+x_{2}}{x_{3}}. Without loss of generality, assume x3=x_{3}= max⁡{x1,x2,x3}\max \left\{x_{1}, x_{2}, x_{3}\right\}, then x1+x2x3⩽2\frac{x_{1}+x_{2}}{x_{3}} \leqslant 2. By assumption, x1+x2x3\frac{x_{1}+x_{2}}{x_{3}} is a natural number, so there are only two cases.
(i) x1+x2x3=2\frac{x_{1}+x_{2}}{x_{3}}=2, and by x3=max⁡{x1,x2,x3}x_{3}=\max \left\{x_{1}, x_{2}, x_{3}\right\}, we know x1=x2=x3x_{1}=x_{2}=x_{3}, so s3=6<9s_{3}=6<9.
(ii) x1+x2x3=1\frac{x_{1}+x_{2}}{x_{3}}=1, let P=x2+x3x1,q=x3+x1x2P=\frac{x_{2}+x_{3}}{x_{1}}, q=\frac{x_{3}+x_{1}}{x_{2}}, then p,qp, q are natural numbers and
2x2=(p−1)x1,2x1=(q−1)x2.2 x_{2}=(p-1) x_{1}, 2 x_{1}=(q-1) x_{2} .

Since x1x_{1} and x2x_{2} are positive, P−1⩾1,q−1⩾1P-1 \geqslant 1, q-1 \geqslant 1 and
(p−1)(q−1)=4(p-1)(q-1)=4

If p−1=4,q−1=1p-1=4, q-1=1 or p−1=1,q−1=4p-1=1, q-1=4, then s3=1+p+qs_{3}=1+p+q =8<9=8<9, if p−1=2,q−1=2p-1=2, q-1=2, then s3=1+p+q=7<9s_{3}=1+p+q=7<9. In any case, s3<9s_{3}<9.

Assume when n=kn=k, sk<3ks_{k}<3 k. When n=k+1n=k+1,
sk+1=x1+x3x2+⋯+xk−2+xkxk−1+xk−1+xk+1xk+xk+x1xk+1+xk+1+x2x1.\begin{aligned} s_{k+1}= & \frac{x_{1}+x_{3}}{x_{2}}+\cdots+\frac{x_{k-2}+x_{k}}{x_{k-1}}+\frac{x_{k-1}+x_{k+1}}{x_{k}}+\frac{x_{k}+x_{1}}{x_{k+1}}+ \\ & \frac{x_{k+1}+x_{2}}{x_{1}} . \end{aligned}

Without loss of generality, assume xk+1=max⁡{x1,x2,⋯ ,xk,xk+1}x_{k+1}=\max \left\{x_{1}, x_{2}, \cdots, x_{k}, x_{k+1}\right\}, then
sk+1=x1+x3x2+…+xk−2+xkxk−1+xk−1+x1xk+xk+x2x1−xk−1+x1xk−xk+x2x1+xk−1+xk+1xk+xk+x1xk+1+xk+1+x2x1.\begin{aligned} s_{k+1}= & \frac{x_{1}+x_{3}}{x_{2}}+\ldots+\frac{x_{k-2}+x_{k}}{x_{k-1}}+\frac{x_{k-1}+x_{1}}{x_{k}}+\frac{x_{k}+x_{2}}{x_{1}} \\ & -\frac{x_{k-1}+x_{1}}{x_{k}}-\frac{x_{k}+x_{2}}{x_{1}}+\frac{x_{k-1}+x_{k+1}}{x_{k}}+\frac{x_{k}+x_{1}}{x_{k+1}}+ \\ & \frac{x_{k+1}+x_{2}}{x_{1}} . \end{aligned}

By assumption, xk+x1xk+1\frac{x_{k}+x_{1}}{x_{k+1}} is a natural number, so there are only two cases.
(1) x1+xkxk+1=2\frac{x_{1}+x_{k}}{x_{k+1}}=2. By xk+1=max⁡{x1,x2,⋯ ,xk,xk+1}x_{k+1}=\max \left\{x_{1}, x_{2}, \cdots, x_{k}, x_{k+1}\right\}, we get xk=x_{k}= xk+1=x1x_{k+1}=x_{1}, thus x1,x2,⋯ ,xkx_{1}, x_{2}, \cdots, x_{k} also satisfy the conditions, i.e., the ratio of the sum of the two adjacent numbers to the number itself is a natural number. By the induction hypothesis, we have
sk+1<3k−xk−1+x1xk−xk+x2x1+xk−1+xk+1xk+xk+x1xk+1+xk+1+x2x1=3k+2<3(k+1).\begin{aligned} s_{k+1}< & 3 k-\frac{x_{k-1}+x_{1}}{x_{k}}-\frac{x_{k}+x_{2}}{x_{1}}+\frac{x_{k-1}+x_{k+1}}{x_{k}}+\frac{x_{k}+x_{1}}{x_{k+1}}+ \\ & \frac{x_{k+1}+x_{2}}{x_{1}} \\ = & 3 k+2<3(k+1) . \end{aligned}
(2) x1+xkxk+1=1\frac{x_{1}+x_{k}}{x_{k+1}}=1, i.e., xk+1=x1+xkx_{k+1}=x_{1}+x_{k}. Since xk−1+xk+1xk,xk+1+x2x1\frac{x_{k-1}+x_{k+1}}{x_{k}}, \frac{x_{k+1}+x_{2}}{x_{1}} are

natural numbers and x1,x2,⋯ ,xk,xk+1x_{1}, x_{2}, \cdots, x_{k}, x_{k+1} are natural numbers, xk−1+x1xk,xk+x2x1\frac{x_{k-1}+x_{1}}{x_{k}}, \frac{x_{k}+x_{2}}{x_{1}} are also natural numbers. By the induction hypothesis, we have
sk+1<3k−xk−1+x1xk−xk+x2x1+xk−1+xk+1xk+xk+x1xk+1+xk+1+x2x1=3k+1+xk+1−x1xk+xk+1−xkx1=3(k+1),\begin{array}{l} s_{k+1} \\ <3 k-\frac{x_{k-1}+x_{1}}{x_{k}}-\frac{x_{k}+x_{2}}{x_{1}}+\frac{x_{k-1}+x_{k+1}}{x_{k}}+\frac{x_{k}+x_{1}}{x_{k+1}}+\frac{x_{k+1}+x_{2}}{x_{1}} \\ =3 k+1+\frac{x_{k+1}-x_{1}}{x_{k}}+\frac{x_{k+1}-x_{k}}{x_{1}} \\ =3(k+1), \end{array}

i.e., sk+1<3(k+1)s_{k+1}<3(k+1).
Therefore, for any natural number n⩾3n \geqslant 3, sn<3ns_{n}<3 n.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.