# 2000 IMO Problems/Problem 4

## 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.)

## Solution

Consider $1$, $2$ and $3$. If they are in different boxes, then $4$ must be in the same box as $1$, $5$ in the same box as $2$ and so on. This leads to the solution where all numbers congruent to each other mod $3$ are in the same box.

Suppose $1$ and $2$ are in box $A$ and $3$ in box $B$. Then $4$ must be in box $A$ or $B$. In general, if $k\ge 4$ is in either box $A$ or $B$, then $k + 1$ also must be in box $A$ or $B$. Thus box $C$ is empty which is impossible.

Similarly, it is impossible for $1$ and $3$ to be in box $A$ and $2$ in box $B$.

Thus we are left with the case where $1$ is in box $A$ and $2$ and $3$ in box $B$. Suppose box $B$ contains $2, . . . k$, where $k \ge 3$, but does not contain $k + 1$ and $m$ is the smallest number in box $C$. Then $m > k$.

If $m > k + 1$, then $k + 1$ must be box $A$ and we see that no box can contain $m-1$.

Thus $m = k + 1$. If $k < 99$, we see that no box can contain $k + 2$. Thus $k = 99$. It is easy to see that this distribution works. Thus there altogether $12$ ways - $2$ options times permutation of $3$ colors for each of $3$ boxes.