Maths Olympiad Prep

Library / /182 of 520

Number theory Difficulty 6.2 National olympiad Find the answer

For any set A={a1,a2,a3,a4}A=\left\{a_{1}, a_{2}, a_{3}, a_{4}\right\} of four distinct positive integers with sum sA=a1+a2+a3+a4s_{A}=a_{1}+a_{2}+a_{3}+a_{4}, let pAp_{A} denote the number of pairs (i,j)(i, j) with 1i<j41 \leq i<j \leq 4 for which ai+aja_{i}+a_{j} divides sAs_{A}. Among all sets of four distinct positive integers, determine those sets AA for which pAp_{A} is maximal.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Firstly, we will prove that the maximum value of pAp_{A} is at most 4. Without loss of generality, we may assume that a1a1+a3a_{1}a_{1}+a_{3} and a3+a4>a1+a2a_{3}+a_{4}>a_{1}+a_{2}. Hence a2+a4a_{2}+a_{4} and a3+a4a_{3}+a_{4} do not divide sAs_{A}. This proves pA4p_{A} \leq 4. Now suppose pA=4p_{A}=4. By the previous argument we have
a1+a4a2+a3 and a2+a3a1+a4,a1+a2a3+a4 and a3+a4̸a1+a2,a1+a3a2+a4 and a2+a4̸a1+a3. \begin{array}{lll} a_{1}+a_{4} \mid a_{2}+a_{3} & \text { and } & a_{2}+a_{3} \mid a_{1}+a_{4}, \\ a_{1}+a_{2} \mid a_{3}+a_{4} & \text { and } & a_{3}+a_{4} \not a_{1}+a_{2}, \\ a_{1}+a_{3} \mid a_{2}+a_{4} & \text { and } & a_{2}+a_{4} \not a_{1}+a_{3}. \end{array}
Hence, there exist positive integers mm and nn with m>n2m>n \geq 2 such that
{a1+a4=a2+a3m(a1+a2)=a3+a4n(a1+a3)=a2+a4 \left\{\begin{array}{l} a_{1}+a_{4}=a_{2}+a_{3} \\ m\left(a_{1}+a_{2}\right)=a_{3}+a_{4} \\ n\left(a_{1}+a_{3}\right)=a_{2}+a_{4} \end{array}\right.
Adding up the first equation and the third one, we get n(a1+a3)=2a2+a3a1n\left(a_{1}+a_{3}\right)=2 a_{2}+a_{3}-a_{1}. If n3n \geq 3, then n(a1+a3)>3a3>2a2+a3>2a2+a3a1n\left(a_{1}+a_{3}\right)>3 a_{3}>2 a_{2}+a_{3}>2 a_{2}+a_{3}-a_{1}. This is a contradiction. Therefore n=2n=2. If we multiply by 2 the sum of the first equation and the third one, we obtain
6a1+2a3=4a2 6 a_{1}+2 a_{3}=4 a_{2}
while the sum of the first one and the second one is
(m+1)a1+(m1)a2=2a3. (m+1) a_{1}+(m-1) a_{2}=2 a_{3}.
Adding up the last two equations we get
(m+7)a1=(5m)a2. (m+7) a_{1}=(5-m) a_{2}.
It follows that 5m15-m \geq 1, because the left-hand side of the last equation and a2a_{2} are positive. Since we have m>n=2m>n=2, the integer mm can be equal only to either 3 or 4. Substituting (3,2)(3,2) and (4,2)(4,2) for (m,n)(m, n) and solving the previous system of equations, we find the families of solutions {d,5d,7d,11d}\{d, 5 d, 7 d, 11 d\} and {d,11d,19d,29d}\{d, 11 d, 19 d, 29 d\}, where dd is any positive integer.

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

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