IMO 2011 · Problem 1

Given any set \(A=\{a_1,a_2,a_3,a_4\}\) of four distinct positive integers, we denote the sum \(a_1+a_2+a_3+a_4\) by \(s_A\). Let \(n_A\) denote the number of pairs \((i,j)\) with \(1\le i<j\le4\) for which \(a_i+a_j\) divides \(s_A\). Find all sets \(A\) of four distinct positive integers which achieve the largest possible value of \(n_A\).

Official text of the problem. Official problem paper (PDF)

Answer

The largest possible value is \(\boxed{4}\). All sets attaining it are \[ \boxed{A=\{k,5k,7k,11k\}\quad\text{or}\quad A=\{k,11k,19k,29k\},\qquad k\in\mathbb Z_{>0}.} \]

Solution

Write the elements of \(A\) in increasing order as \[ a<b<c<d, \] and put \(S=a+b+c+d\).

Every pair sum is less than \(S\), so any pair sum dividing \(S\) must be at most \(S/2\). Since \[ b+d>a+c,\qquad c+d>a+b, \] both \(b+d\) and \(c+d\) exceed \(S/2\). Thus neither divides \(S\), and consequently \[ n_A\le4. \]

We determine all sets for which equality holds, then verify that they attain it.

Suppose \(n_A=4\). The other four pair sums, \[ a+b,\quad a+c,\quad a+d,\quad b+c, \] must all divide \(S\). In particular, \(a+d\) and \(b+c\) are each at most \(S/2\). Their sum is \(S\), so \[ a+d=b+c=\frac S2. \]

Define the positive integers \[ p=\frac{S}{a+b},\qquad q=\frac{S}{a+c}. \] Because \(a+b<a+c<b+c=S/2\), we have \(p>q\ge3\). Moreover, \[ \frac1p+\frac1q =\frac{(a+b)+(a+c)}{S} =\frac{2a+b+c}{S} =\frac12+\frac{2a}{S} >\frac12. \] If \(q\ge4\), then \(p\ge5\), giving \[ \frac1p+\frac1q\le\frac15+\frac14=\frac9{20}<\frac12, \] a contradiction. Hence \(q=3\), and the strict inequality above becomes \[ \frac1p>\frac16. \] Together with \(p>3\), this gives \(p=4\) or \(p=5\).

If \(p=4\), then \[ 2a=(a+b)+(a+c)-(b+c) =\frac S4+\frac S3-\frac S2 =\frac S{12}. \] Thus \(S=24a\), and \[ b=\frac S4-a=5a,\qquad c=\frac S3-a=7a,\qquad d=\frac S2-a=11a. \] Therefore \(A=\{a,5a,7a,11a\}\).

If \(p=5\), similarly, \[ 2a=\frac S5+\frac S3-\frac S2=\frac S{30}. \] Thus \(S=60a\), and \[ b=\frac S5-a=11a,\qquad c=\frac S3-a=19a,\qquad d=\frac S2-a=29a. \] Therefore \(A=\{a,11a,19a,29a\}\).

Finally, both families consist of four distinct positive integers. For \[ A=\{k,5k,7k,11k\}, \] the total is \(24k\), and the four pair sums \(6k,8k,12k,12k\) all divide it. For \[ A=\{k,11k,19k,29k\}, \] the total is \(60k\), and the four pair sums \(12k,20k,30k,30k\) all divide it. Each repeated sum comes from two different pairs.

Hence both families have \(n_A=4\), proving the maximum and the complete classification.

The solution was checked against the official IMO shortlist solutions.