2000 IMO Problems/Problem 4
A magician has one hundred cards numbered to . 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.)
Consider , and . If they are in different boxes, then must be in the same box as , in the same box as and so on. This leads to the solution where all numbers congruent to each other mod are in the same box.
Suppose and are in box and in box . Then must be in box or . In general, if is in either box or , then also must be in box or . Thus box is empty which is impossible.
Similarly, it is impossible for and to be in box and in box .
Thus we are left with the case where is in box and and in box . Suppose box contains , where , but does not contain and is the smallest number in box . Then .
If , then must be box and we see that no box can contain .
Thus . If , we see that no box can contain . Thus . It is easy to see that this distribution works. Thus there altogether ways - options times permutation of colors for each of boxes.