IMO 2011 Problem 1

[Moon]

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 \leq i < j \leq 4$ 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$.

[Masum]

There are total $6$ possible pairs such that $1\le i< j\le4$. The expressions are symmetric. Let's assume without loss of generality, $a_1<a_2<a_3<a_4$ because they are distinct. Since $a_2+a_4|s_A=a_1+a_2+a_3+a_4\to a_2+a_4|a_1+a_3<a_2+a_4$, and the same holds for $a_3+a_4$. Therefore, $n_{A}=4$.
$a_1+a_4|a_2+a_3\to a_1+a_4\le a_2+a_3$, if $a_2+a_3<s<2(a_2+a_3)$, $s$ is not a multiple of $a_2+a_3$. So $a_1+a_4=a_2+a_3=k,s=2k$. This shows that the set is $\{a,b,d-a,d-b\}$ for some $a,b$.
We have $d-b+a|d+b-a\to d-b+a|2d$ and $a+b|2d-a-b\to a+b|2d$. From the first, if $d+a-b|d-a+b$ we easily conclude from $\frac{a_2+a_4}{a_1+a_3}=l,l=2\to d=3(b-a)$ or $d=a+b$ gives the solution $a+b=2(a-b)\to b=3a\to a=1,b=3$. Then $a+b=4|2d\to d=2k$ is a solution.
Else $d=3(b-a)\to a+b|6(b-a)\to a+b|12a\to 1<a+b|12\to a+b=3,6,12$. We have three cases $a=1,b=2,3|d$ giving $\{1,2,3k-2,3k-1\}$.
Or, $a=1,b=5$ as $\gcd(a,b)=1$. Then $6|2d\to d=3k$ giving $\{1,5,3k-5,3k-1\}$.
Else $a=1,b=11,6|d$ gives $\{1,11,6k-11,6k-1\}$.
They are all solutions.ion.
Else $d=3(b-a)\to a+b|6(b-a)\to a+b|12a\to 1<a+b|12\to a+b=3,6,12$. We have three cases $a=1,b=2,3|d$ giving $\{1,2,3k-2,3k-1\}$.
Or, $a=1,b=5$ as $\gcd(a,b)=1$. Then $6|2d\to d=3k$ giving $\{1,5,3k-5,3k-1\}$.
Else $a=1,b=11,6|d$ gives $\{1,11,6k-11,6k-1\}$.
Now use the fact $a_1+a_3|a_2+a_4$ and find the complete solutions.

Note: This year IMO problems 1 and 5 both use the same idea.

[Tahmid Hasan]

since $a_1,a_2,a_3,a_4$ are distinct positive integers without loss of generality we may assume
$a_1<a_2<a_3<a_4$
now the six possible cases are
a.$a_1+a_2 \mid s_a$ or, $a_1+a_2 \mid a_3+a_4$
b.$a_1+a_3 \mid s_a$ or,$a_1 +a_3 \mid a_2+a_4$
c.$a_1+a_4 \mid s_a$ or,$a_1+a_4 \mid a_2+a_3$
d.$a_2+a_3 \mid s_a$ or, $a_2+a_3 \mid a_1+a_4$
e.$a_2+a_4 \mid s_a$ or, $a_2+a_4 \mid a_1+a_3$
f.$a_3+a_4 \mid s_a$ or, $a_3+a_4 \mid a_1+a_2$
but $a_2>a_1,a_4>a_3$ so,$a_2+a_4>a_1a_3$
and $a_3>a_1,a_4>a_2$ so,$a_3+a_4>a_1+a_2$
so e. and f. are not possible,now we consider the case
$n_a=4$
the cases we have now are
1. $a_1+a_2 \mid a_3+a_4$
2.$a_1 +a_3 \mid a_2+a_4$
3.$a_1+a_4 \mid a_2+a_3$
4. $a_2+a_3 \mid a_1+a_4$
from 3. and 4. we get $a_2+a_3=a_1+a_4$ or $a_2+a_3=-(a_1+a_4)$
but both sides are natural,so the second condition is not possible.
so we have
$a_2+a_3=a_1+a_4$
or,$a_2-a_1=a_4-a_3$
or,$a_3-a_1=a_4-a_2$
from this we can deduce ${a_1,a_2,a_3,a_4}={a_1,a_1+k_1,a_1+k_2,a_1+k_1+k_2}$......(x)
where $k_1,k_2$ are natural numbers.
inputting these values in 1. and 2. we get
1.a.$2a_1+k_1 \mid 2k_2$ or,$(2a_1+k_1)p_1=2k_2$........(s)[p_1 is a natural number]
2.a.$2a_1+k_2 \mid 2k_1$ or,$(2a_1+k_2)p_2= 2k_1$.......(t)[p_2 is a natural number]
now we input the value of $k_2$ from (s) to (t)
and get $2a_1p_2(2+p_1)=k_1(4-p_1p_2)$........(u)
since the left side of (u) is positive then the right side is also positive
so $0<p_1p_2<1$
now the possible cases are
c1.$p_1=1,p_2=2$
c2.$p_1=2,p_2=1$
c3.$p_1=1,p_2=1$
c4.$p_1=1,p_2=3$
c5.$p_1=3,p_2=1$
first we input these values in (u) and get the value of $k_1$ wrt $a_1$
now we input the values in (t) and get the value of $k_2$ wrt $a_1$
now we input the value of $k_1,k_2$ in (x) and the five results from which c1,c3,c4 are not possible after doing verification.
then the two desired results are
c2.${a_1,a_1,a_1,a_1}={a_1,5a_1,7a_1,11a_1}$
c5.${a_1,a_1,a_1,a_1}={a_1,11a_1,19a_1,29a_1}$

[Masum]

Well done!

[Labib]

Let's assume without loss of generality, $a_1<a_2<a_3<a_4$ because the numbers are distinct.

Now, it's visible that $a_3+a_4$ , $a_2+a_4 > \frac {1}{2} S_A$ and therefore do not devide $S_A$.
So $n_A \leq 4$.
If ${a_1+a_4}$ is not equal to ${a_2+a_3}$, $a_1+a_4$ or $a_2+a_3$ will be greater than $\frac {1}{2}S_A$ and won't divide it.
So, to get $n_A$'s max value $(4)$, $a_1+a_4$ has to be equal to $a_2+a_3$.

So, ${a_1+a_4} = {a_2+a_3}$ ................... $(1)$

Again, ${a_2+a_4} = k(a_1+a_3)$............... $(2)$
and ${a_3+a_4} = m(a_1+a_2)$............... $(3)$
where $m,k \in N$ and $m,k > 1$.

From $(2)$, we get -
$a_2+a_2+a_3-a_1=k.a_1+k.a_3 $
$\Rightarrow (k+1)a_1+(k-1)a_3=2a_2$ ................ $(4)$
As $2a_3>2a_2$, so $(k-1)=1$.
Therefore, $a_3=2a_2-3a_1$............ $(5)$
and $a_4=3a_2-4a_1$............ $(6)$ [From $(1)$]

Again, From $(3)$ we get -
${5a_2-7a_1} = m(a_1+a_2) $
$\Rightarrow (m+7)a_1 = (5-m)a_2$.................... $(7)$

As, $1 \leq (5-m) \leq 3$,
$m$ has $3$ possible values. $(2,3,4)$

Putting $m=2$ in $(5)$, we deduce $a_2=a_3$ which is not possible. So $m$ is not equal to $2$.

Then, putting $m=3$ in $(5),(6)$ and $(7)$ we get -
$A$=$\left \{ a_1,5a_1,7a_1,11a_1 \right \}$.

And putting $m=3$ in $(5),(6)$ and $(7)$ we get -
$A$=$\left \{ a_1,11a_1,19a_1,29a_1 \right \}$.

These two sets represent all such sets $A$ which satisfy the given requirements.