Olympiad Maths Prep

Track / Stage 9 / 21 of 80 #1901 of 2000

Problem 1901

IMO P2/P5; hard shortlist
Number theory Difficulty 9.1 Prove it China National Team Selection Test · China

Given any nn (>1> 1) coprime positive integers a1,a2,,ana_1, a_2, \dots, a_n, denote A=a1+a2++anA = a_1 + a_2 + \dots + a_n. Let di=(A,ai)d_i = (A, a_i) (the greatest common divisor), i=1,2,,ni = 1, 2, \dots, n.
Let DiD_i be the greatest common divisor of {a1,a2,,an}{ai}\{a_1, a_2, \dots, a_n\} \setminus \{a_i\}, i=1,2,,ni = 1, 2, \dots, n. Find the minimum of i=1nAaidiDi\prod_{i=1}^n \frac{A - a_i}{d_i D_i}.
(posed by Zhang Sihui)

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

Consider
D1=(a2,a3,,an) and d2=(a2,A)=(a2,a1+a2++an). D_1 = (a_2, a_3, \dots, a_n) \text{ and } d_2 = (a_2, A) = (a_2, a_1 + a_2 + \dots + a_n).
Let (D1,d2)=d(D_1, d_2) = d. Then da2,da3,,dan,da1+a2++and \mid a_2, d \mid a_3, \dots, d \mid a_n, d \mid a_1 + a_2 + \dots + a_n. Thus, da1d \mid a_1. Consequently,
d(a1,a2,,an). d \mid (a_1, a_2, \dots, a_n).
Since a1,a2,,ana_1, a_2, \dots, a_n are coprime, we have d=1d = 1. Note that D1a2,D2a2D_1 \mid a_2, D_2 \mid a_2 and (D1,D2)=1(D_1, D_2) = 1. We have D1d2a2D_1 d_2 \mid a_2. So D1d2a2D_1 d_2 \le a_2. Similarly, we have D2d3a3,,Dnd1a1D_2 d_3 \le a_3, \dots, D_n d_1 \le a_1. Hence,
i=1ndiDi=(D1d2)(D2d3)(Dnd1)a2a3ana1=i=1nai.1 \begin{aligned} \prod_{i=1}^{n} d_i D_i &= (D_1 d_2) \cdot (D_2 d_3) \cdot \dots \cdot (D_n d_1) \\ &\le a_2 a_3 \dots a_n a_1 \\ &= \prod_{i=1}^{n} a_i. \end{aligned} \qquad \textcircled{1}
Considering
i=1n(Aai)=i=1n(jiaj)i=1n((n1)(jiaj)1n1)=(n1)ni=1nai2 \begin{aligned} \prod_{i=1}^{n} (A - a_i) &= \prod_{i=1}^{n} \left( \sum_{j \neq i} a_j \right) \\ &\geq \prod_{i=1}^{n} \left( (n-1) \left( \prod_{j \neq i} a_j \right)^{\frac{1}{n-1}} \right) \\ &= (n-1)^n \cdot \prod_{i=1}^{n} a_i \end{aligned} \qquad \textcircled{2}
and by ① and ②, we see that
i=1nAaidiDi(n1)n. \prod_{i=1}^{n} \frac{A - a_i}{d_i D_i} \ge (n-1)^n.
On the other hand, if a1=a2==an=1a_1 = a_2 = \dots = a_n = 1,
i=1nAaidiDi=(n1)n. \prod_{i=1}^{n} \frac{A - a_i}{d_i D_i} = (n - 1)^n.
Summing up, the minimum of i=1nAaidiDi\prod_{i=1}^{n} \frac{A - a_i}{d_i D_i} is (n1)n(n - 1)^n.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.