2000 IMO Problems/Problem 4
Problem
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.)
Solution
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.
Taken from: https://sms.math.nus.edu.sg/Simo/IMO_Problems/00.pdf