Maths Olympiad Prep

Library / China National Team Selection Test /45 of 46

China National Team Selection Test

Number theory Difficulty 9.1 IMO level Prove it 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=1nA−aidiDi\prod_{i=1}^n \frac{A - a_i}{d_i D_i}.
(posed by Zhang Sihui)

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 d∣a2,d∣a3,…,d∣an,d∣a1+a2+⋯+and \mid a_2, d \mid a_3, \dots, d \mid a_n, d \mid a_1 + a_2 + \dots + a_n. Thus, d∣a1d \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 D1∣a2,D2∣a2D_1 \mid a_2, D_2 \mid a_2 and (D1,D2)=1(D_1, D_2) = 1. We have D1d2∣a2D_1 d_2 \mid a_2. So D1d2≤a2D_1 d_2 \le a_2. Similarly, we have D2d3≤a3,…,Dnd1≤a1D_2 d_3 \le a_3, \dots, D_n d_1 \le a_1. Hence,
∏i=1ndiDi=(D1d2)⋅(D2d3)⋅⋯⋅(Dnd1)≤a2a3…ana1=∏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(A−ai)=∏i=1n(∑j≠iaj)≥∏i=1n((n−1)(∏j≠iaj)1n−1)=(n−1)n⋅∏i=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=1nA−aidiDi≥(n−1)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=1nA−aidiDi=(n−1)n. \prod_{i=1}^{n} \frac{A - a_i}{d_i D_i} = (n - 1)^n.
Summing up, the minimum of ∏i=1nA−aidiDi\prod_{i=1}^{n} \frac{A - a_i}{d_i D_i} is (n−1)n(n - 1)^n.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.