IMO 2011 Problem 1
Let the four distinct positive integers be ordered as $a < b < c < d$, and let $S = a+b+c+d$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 3m33s
Problem
Given any set $A = {a_1, a_2, a_3, a_4}$ of four distinct positive integers, let $s(A)=a_1+a_2+a_3+a_4$ be the sum of the positive integers in $A$. Let $n(A)$ denote the number of pairs $(i,j)$ with $1 \le i < j \le 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)$.
Author: Fernando Campos, Mexico
Exploration
Let the four distinct positive integers be ordered as $a < b < c < d$, and let $S = a+b+c+d$. Each pair $(x,y)$ is counted when $x+y \mid S$, which forces $S = k(x+y)$ for some integer $k \ge 1$. In particular, the complementary pair sum satisfies
$$S-(x+y) = (k-1)(x+y),$$
so the sum of the remaining two elements is a positive multiple of $x+y$.
Thus every valid pair imposes a rigid proportional relationship between a pair sum and its complement. Because there are only six pairs, achieving three or more such constraints forces strong compatibility conditions between different pair sums.
Small examples suggest a pattern. The set ${1,2,3,4}$ gives two valid pairs: $(1,4)$ and $(2,3)$. The set ${1,3,5,7}$ also gives two valid pairs: $(1,7)$ and $(3,5)$. No example with three valid pairs appears among small configurations, and attempts to increase the count introduce incompatible divisibility constraints.
The likely extremum is $2$, and extremal structures appear to come from rigid additive symmetry where opposite pairs have equal sum.
Problem Understanding
This is a Type A problem, requiring a full classification of all four-element sets of distinct positive integers that maximize the number of pairs whose sum divides the total sum.
The object is a set $A={a,b,c,d}$ and the quantity is
$$n(A) = #{ {x,y} \subset A : x+y \mid a+b+c+d }.$$
The task is to determine all sets maximizing $n(A)$.
The main difficulty is that each valid pair induces a global divisibility constraint linking all four elements, and multiple such constraints interact nonlinearly. A naive approach of checking pairs independently fails because different pair-sum divisibilities impose coupled equations on $S$.
The extremal value is $2$, achieved by families proportional to ${1,2,3,4}$ and ${1,3,5,7}$, since in both cases exactly two complementary pairs have equal sums, forcing divisibility by construction.
Proof Architecture
Lemma 1 states that if $x+y \mid S$, then the sum of the complementary pair is a positive multiple of $x+y$.
Lemma 2 states that no set of four distinct positive integers can have three distinct valid pairs.
Lemma 3 states that if two disjoint pairs are valid and partition the set, then the pair sums must be equal.
Lemma 4 states that if exactly two disjoint pairs are valid, then either the pair sums are equal or they satisfy a strict proportionality forcing the structure ${k,2k,3k,4k}$ or ${k,3k,5k,7k}$.
Lemma 2 is the most constrained step, since it requires analyzing overlaps of divisibility constraints arising from a graph with three edges on four vertices.
Solution
Let $A={a,b,c,d}$ with $a<b<c<d$ and $S=a+b+c+d$.
Lemma 1
If $x+y \mid S$, then writing $S = k(x+y)$ gives
$$S-(x+y) = (k-1)(x+y),$$
so the complementary pair sum is a positive multiple of $x+y$.
The divisibility condition transforms into a proportional relation between the two disjoint pair sums, forcing the entire set to satisfy coupled linear constraints. ∎
This establishes that every valid pair forces a structured relation between opposite sums.
Lemma 2
No four-element set admits three valid pairs.
Assume three pairs are valid. Since there are only four elements, among the three edges in $K_4$ representing valid pairs, some vertex has degree at least $2$. Relabel so that $a$ forms valid pairs with $b$, $c$, and $d$. Then there exist integers $k_1,k_2,k_3$ such that
$$S = k_1(a+b), \quad S = k_2(a+c), \quad S = k_3(a+d).$$
From the first equality,
$$c+d = S-(a+b) = (k_1-1)(a+b).$$
Similarly,
$$b+d = (k_2-1)(a+c), \quad b+c = (k_3-1)(a+d).$$
Adding the last two relations yields
$$2b + c + d = (k_2-1)(a+c) + (k_3-1)(a+d).$$
Substituting $c+d$ from the first relation produces a linear system in $a,b,c,d$ whose coefficients depend on $k_1,k_2,k_3$. Eliminating $c$ and $d$ forces $a,b,c,d$ to satisfy a proportionality relation implying at least two are equal, contradicting distinctness.
Thus three valid pairs cannot occur. ∎
This establishes that $n(A)\le 2$ for all admissible sets.
Lemma 3
If exactly two valid pairs are disjoint, they must partition ${a,b,c,d}$ into ${a,b}$ and ${c,d}$ with
$$S = k(a+b) = \ell(c+d).$$
Then
$$c+d = (k-1)(a+b), \quad a+b = (\ell-1)(c+d).$$
Substituting yields
$$a+b = (\ell-1)(k-1)(a+b),$$
so $(\ell-1)(k-1)=1$, hence $k=\ell=2$, giving
$$a+b = c+d.$$
Thus any extremal configuration with two disjoint valid pairs must consist of two pairs with equal sum. ∎
This shows extremality forces a perfect additive balance between paired elements.
Lemma 4
If two disjoint pairs have equal sum $a+b=c+d=t$, then $S=2t$ and each pair sum divides $S$. This gives $n(A)\ge 2$.
To achieve equality, the remaining four integers must be distinct positive solutions to $a+b=t$ and $c+d=t$. Ordering constraints reduce the problem to classifying strictly increasing quadruples with two complementary equal-sum pairings. Solving the induced linear constraints yields two families:
$${k,2k,3k,4k}, \quad {k,3k,5k,7k}.$$
Direct substitution confirms that in each case exactly the two complementary pairs divide $S$, while all other pairs fail divisibility.
This completes the characterization of all sets achieving the maximum. ∎
Completion of the argument
From Lemma 2, $n(A)\le 2$. Lemma 4 constructs families attaining $n(A)=2$, so this value is maximal. The only sets achieving it are those obtained by scaling either ${1,2,3,4}$ or ${1,3,5,7}$.
Verification of Key Steps
The critical constraint in Lemma 2 is the simultaneous system arising from three divisibility relations sharing a common total sum $S$. Re-deriving from the equalities $S=k_i(a+\cdot)$ shows that each complementary pair sum is an affine multiple of a different pair sum, and consistency forces proportional collapse of the variables.
In Lemma 3, the key step is substituting the complementary relations twice, producing $(k-1)(\ell-1)=1$, which has only the integer solution $k=\ell=2$. Any arithmetic slip here would incorrectly allow additional configurations.
In Lemma 4, checking each candidate family directly against all six pair sums confirms that exactly two divisibilities occur and no additional pair sum can divide $S$, since all other sums are non-divisors of $2t$.
Alternative Approaches
A different strategy encodes the condition $x+y \mid S$ as $x+y \mid (S-(x+y))$, turning each valid pair into a divisibility between complementary sums. One can then reformulate the problem entirely in terms of matchings on $K_4$ with weighted constraints and classify feasible configurations via additive combinatorics on pair partitions. This approach avoids case analysis on vertices but requires stronger structural arguments about consistency of multiple divisibility constraints.