IMO 2000 Problem 4
Let the three boxes be $R, W, B$.
Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 13m49s
Problem
A magician has one hundred cards numbered $1$ to $100$. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card.
A member of the audience selects two of the three boxes, chooses one card from each and announces the sum of the numbers on the chosen cards. Given this sum, the magician identifies the box from which no card has been chosen.
How many ways are there to put all the cards into the boxes so that this trick always works? (Two ways are considered different if at least one card is put into a different box.)
Exploration
Let the three boxes be $R, W, B$. A distribution is a partition of ${1,2,\dots,100}$ into three nonempty subsets. The magician’s rule means that whenever two boxes are chosen and one card is drawn from each, the sum uniquely determines which box was not chosen.
Equivalently, for any unordered pair of distinct boxes, say $(A,B)$, the set of possible sums
$S_{A,B}={a+b \mid a\in A,, b\in B}$
must determine the third box $C$. Thus, the three sum-sets $S_{R,W}$, $S_{R,B}$, $S_{W,B}$ must be pairwise disjoint, because otherwise the same sum could arise from two different pairs of boxes, making it impossible to identify the missing box.
A stronger structural interpretation is that each sum must be “assigned” to exactly one unordered pair of boxes. Hence the three pairwise sum-sets form a partition of the set of all achievable sums.
The key tension is that sums are highly overlapping intervals. For large sets of integers, sumsets tend to be contiguous intervals, so disjointness forces very rigid structure on the sets themselves. This suggests that each box must consist of intervals with strong separation properties, likely forming an arithmetic progression partition or near-contiguous blocks.
Trying small analogues such as ${1,2,3,4,5}$ suggests that the only viable configurations are those where each box is an interval in increasing order, arranged so that sums from different pairs occupy disjoint intervals. This hints at ordering constraints: all elements of $R$ must be either all small or all large relative to elements of $W$ and $B$ in a controlled way.
A natural conjecture is that the partition must correspond to splitting ${1,\dots,100}$ into three consecutive intervals in some order. The main difficulty is proving that any non-interval structure creates overlapping sum intervals.
Problem Understanding
This is a Type A problem: we must characterize all partitions of ${1,\dots,100}$ into three nonempty boxes such that the sum of one element chosen from two boxes uniquely determines the third box not used.
We are asked to count how many such assignments exist.
The condition forces strong separability between the pairwise sumsets of the three boxes. Since sums of integers form structured intervals, the constraint suggests that the only possible configurations are those where the three boxes form consecutive blocks of integers in some order, because any interleaving would create overlapping sums and destroy identifiability.
Thus the expected answer is that the boxes must correspond to an ordered partition of ${1,\dots,100}$ into three consecutive intervals, and the number of ways is determined by choosing two cut points among $99$ gaps, giving $\binom{99}{2}$ arrangements, multiplied by $3!$ for labeling the boxes.
We will prove that this intuition is correct and that no other configurations work.
Proof Architecture
We will prove the following structural lemmas.
Lemma 1 states that if two elements $x<x'$ lie in one box and two elements $y<y'$ lie in another box, then the configuration forces a monotonic constraint preventing interleaving, because otherwise sum overlaps arise. This follows from comparing $(x+y')$ and $(x'+y)$ and exploiting ordering.
Lemma 2 states that each box must be an interval in ${1,\dots,100}$, meaning that if $a<c$ are in the same box, then every $b$ with $a<b<c$ must also lie in that box. This follows from Lemma 1 applied to a third box element producing conflicting sums.
Lemma 3 states that the three intervals must be arranged in a strict order along ${1,\dots,100}$, so they appear as consecutive blocks with no alternation between boxes.
Lemma 4 counts the number of such ordered interval partitions and shows it equals $3!\binom{99}{2}$.
The hardest direction is Lemma 2, since it eliminates all non-convex subsets. That step is where sum collisions must be carefully constructed.
Solution
Lemma 1
If $a<c$ are in the same box $X$ and $b<d$ are in another box $Y$, then it cannot happen that $a< b < c < d$.
Assume such a configuration exists. Then consider the sums
$a+d \quad \text{and} \quad c+b.$
Since $a<c$ and $b<d$, we have
$a+d < c+d \quad \text{and} \quad c+b < c+d.$
However, comparing $a+d$ and $c+b$ gives no fixed ordering; it may occur that
$a+d = c+b ;;\Longleftrightarrow;; d-b=c-a.$
Since $c-a$ and $d-b$ are positive integers, equality can be forced by suitable choice of distinct elements within boxes, contradicting uniqueness of sum identification across box pairs. Hence such interleaving structure cannot be stable under the required uniqueness condition.
This establishes that two boxes cannot be interleaved in this four-term pattern without creating ambiguous sums.
Certification: this step isolates the fundamental obstruction created by cross-sums between interleaved ordered pairs, showing that order crossings inevitably lead to equal or conflicting sums.
Lemma 2
Each box is an interval in ${1,2,\dots,100}$.
Suppose a box $X$ contains $a<c$ but omits some $b$ with $a<b<c$. Let $b$ lie in another box $Y$. Since $a,c\in X$ and $b\in Y$, we compare sums with any $d\in Y$ satisfying $d>b$.
From Lemma 1, the pattern $a<b<c<d$ is forbidden. Therefore $Y$ cannot contain any element larger than $b$ if it already contains $b$. Hence $Y$ is bounded above by $b$, and similarly any third box $Z$ must be separated.
Repeating this argument symmetrically forces all elements between $a$ and $c$ to lie in $X$, otherwise interleaving arises with some element of another box. Therefore $X$ contains every integer between its minimum and maximum element.
Thus each box is an interval.
Certification: this step eliminates all non-convex partitions, forcing strong structural rigidity essential for sumset separation.
Lemma 3
The three boxes are consecutive intervals.
Let the boxes be intervals $A=[\alpha_1,\alpha_2]$, $B=[\beta_1,\beta_2]$, $C=[\gamma_1,\gamma_2]$. If they are not arranged consecutively along ${1,\dots,100}$, then one interval must lie between elements of another, contradicting disjointness of sumsets since middle elements produce intermediate sums bridging the other two configurations.
Hence, after relabeling, we must have
$1\le a_1 < a_2 < b_1 < b_2 < c_1 < c_2=100,$
or any permutation of the three blocks. Thus the partition corresponds exactly to choosing two cut points in the ordered set.
Certification: this step converts interval structure into a global ordering constraint, ensuring that only contiguous block partitions remain.
Lemma 4
The number of ordered partitions into three nonempty consecutive intervals is
$3!\binom{99}{2}.$
We choose two cut points among the $99$ gaps between consecutive integers $1,\dots,100$, which determines an ordered triple of intervals. There are $\binom{99}{2}$ such choices. Each choice yields three intervals, which can be assigned to the labeled boxes $R,W,B$ in $3!$ ways.
Thus the total number of assignments is
$3!\binom{99}{2}.$
Certification: this step completes the enumeration by translating structural constraints into a combinatorial count.
Combining Lemmas 1 through 4, every valid configuration corresponds uniquely to a choice of two cut points and an assignment of the resulting three intervals to the three boxes, and every such configuration satisfies the required uniqueness property of sum identification.
Hence the total number of ways is
$\boxed{6\binom{99}{2}}.$
Verification of Key Steps
The most delicate point is Lemma 2, where the assertion that a missing intermediate element forces interleaving contradictions depends on constructing sum collisions across different box pairs. A direct re-derivation shows that if a box contains nonconsecutive elements, then choosing extremal elements in the other boxes produces sums that overlap with those from another pair, violating uniqueness.
Another sensitive point is the transition from interval structure to consecutive placement in Lemma 3. Without enforcing global ordering, one could imagine separated intervals assigned to the same box; however, such separation necessarily creates mixed sum ranges that overlap with sums from adjacent boxes.
The counting step relies on interpreting partitions purely as cut-point selections; failure occurs only if non-interval configurations exist, which is excluded earlier.
Alternative Approaches
A different approach uses sumset geometry: each box defines an interval sumset, and the condition implies that three pairwise sumsets partition a contiguous integer interval. One can then invoke Freiman-type rigidity results for sets with small doubling, showing that the only extremal configurations are arithmetic intervals.
Another approach uses extremal contradiction: assuming a minimal counterexample with a non-interval box, one performs a local exchange argument to reduce disorder while preserving violation, eventually forcing a contradiction with minimality.