IMO 2000 · Problem 4

100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?

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

Answer

\[ \boxed{12} \]

Solution

The required condition is equivalent to the following: whenever two pairs of cards have the same sum and each pair comes from two different boxes, both pairs must use the same two boxes.

Choose a shortest interval of consecutive cards \[ a,a+1,\ldots,b \] containing cards from all three boxes. Denote the boxes containing \(a\) and \(b\) by \(A\) and \(C\), respectively. By minimality, removing either endpoint must remove a box entirely from the interval. Thus \(A\ne C\), neither endpoint’s box occurs in the interior, and all cards \[ a+1,\ldots,b-1 \] lie in the third box \(B\). In particular, \(b-a\ge2\).

We distinguish two cases.

Case 1: \(b-a=2\).

There are three consecutive cards in three different boxes. We show that this forces the box assignment to repeat with period \(3\).

Suppose \(x,x+1,x+2\) lie in distinct boxes \(X,Y,Z\). If \(x+3\le100\), consider \[ x+(x+3)=(x+1)+(x+2). \] The right-hand pair uses boxes \(Y,Z\). If \(x+3\) were outside \(X\), the left-hand pair would use two different boxes, including \(X\), contradicting the required condition. Therefore \(x+3\) lies in \(X\).

Similarly, if \(x>1\), then \[ (x-1)+(x+2)=x+(x+1) \] forces \(x-1\) to lie in \(Z\).

Applying these observations repeatedly in both directions shows that the three boxes are exactly the three residue classes modulo \(3\), assigned to the boxes in some order.

Every such assignment works: the sums of cards from residue classes \(\{0,1\}\), \(\{0,2\}\), and \(\{1,2\}\) are congruent to \(1,2,0\pmod3\), respectively. Hence the sum identifies the unused box. There are \[ 3!=6 \] such assignments.

Case 2: \(b-a\ge3\).

We show that \(a=1\) and \(b=100\).

Suppose \(a>1\). In the equality \[ (a-1)+b=a+(b-1), \] the right-hand pair uses boxes \(A,B\), while \(b\) lies in \(C\). Consequently, \(a-1\) must also lie in \(C\); otherwise the left-hand pair would use a different pair of boxes.

But then the three consecutive cards \(a-1,a,a+1\) lie in \(C,A,B\), respectively. This contradicts our choice of a shortest interval containing all three boxes, since the chosen interval has at least four cards. Thus \(a=1\).

Likewise, if \(b<100\), the equality \[ a+(b+1)=(a+1)+b \] forces \(b+1\) to lie in \(A\). The three consecutive cards \(b-1,b,b+1\) would then lie in \(B,C,A\), again contradicting minimality. Hence \(b=100\).

Thus the boxes contain \[ \{1\},\qquad \{2,3,\ldots,99\},\qquad \{100\}, \] in some order.

Every such assignment works. The sums from the three possible pairs of boxes lie, respectively, in \[ \{3,\ldots,100\},\qquad \{101\},\qquad \{102,\ldots,199\}, \] which are disjoint. There are again \(3!=6\) assignments.

The two cases exhaust all possibilities. Their assignments are distinct, since the second case has singleton boxes whereas the first does not. Therefore the total is \[ 6+6=\boxed{12}. \]

The solution was checked against Evan Chen's published IMO solution notes.