Magician and cards

From IMO 2000, problem 4:

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 draws two cards from two different boxes and announces the sum of numbers on those cards. Given this information, the magician locates the box from which no card has been drawn.

How many ways are there to put the cards in the three boxes so that the trick works?

Solution

There are 12 possible ways to divide the card:
1. RWWW...WWWB (Card 1 goes to red box, card 2 to 99 go to white box, and card 100 goes to blue box) and all of its permutations, for a total of 6 ways.
2. RWBRWBRWB... and all of its permutations, for a total of 6 ways.

We now show that there are no other ways to put the cards. Consider the placement string (RWB string as in the example above). We will divide into two major cases: those with repeating characters, and those without repeating characters.

First, note that if there is a substring "RW" anywhere in the string, we don't allow substring "RB," for otherwise we can have an ambiguous sum of W+R versus R+B. Likewise, if there is a substring "RW" then we don't allow "BW."

Now, suppose there is a repeating substring "WW." Then we can't have a "RB" or "BR" anywhere in the string because there would be an ambiguous sum of R+W versus B+W.

Note that if we already have a "WW" then we can't have a "BB" because "BB" would mean that no "RW" or "WR" can exist, but we already established that no "RB" or "BR" can exist. So combination of "WW" and "BB" altogether would make it impossible for any "R" to exist in the string, a contradiction.

Consider the last B in the string, and call this B'. There are 4 possibilities of strings that come after B':
1. B'B: contradiction because B' is the last B in the string
2. B'R: contradiction because no BR is allowed
3. B'W
4. B' is the last letter in the whole string.

Consider also the last R in the string, call it R'. As in B', we only have 2 possibilities of strings that come after R':
5. R'W
6. R' is the last letter in the whole string.

Now obviously 4 and 6 cannot both be true, so one of them (possibly both) must be false. WLOG, we can assume that 6 is false, then 5 has to be true. If there's RW, we cannot have BW, so 3 is false, which means 4 is true.

So the last R in the string is followed by a W, and B is the last letter in the whole string. Since there already is an RW, we can't have a BW in the entire string. Also, we can't have BB, or BR, so there's no other place for another B. That means B' is the last and only B in the string.

Now, R' can't be preceded by another R (because no RR is allowed), nor by a B (because no BR is allowed), nor by a W, because a WR and a WB' can't both exist. So R' is the earliest R in the string. Since it's also the last, then R' is the only R in the string.

So we have RWW...WWB (and all of its permutations) as the only solution that allows repetition between characters.

Now, suppose there's no repeated characters. We assert that we cannot have a pattern like "RWR" anywhere in the string. Because the character that comes after "RWR" cannot be B, because "RWRB" gives an ambiguous sum of R+B and W+R. We also cannot have RWRR for there's no repeating characters. So we must have either "RWRW" or the fact that RWR is the ending of the entire string. If it is the ending, then we apply the same argument forward, and conclude that the ending must be WRWR. Either way, an RWR can be extended to RWRW or WRWR. But since there is at least one B in the string, and this B cannot be adjacent to another B, and we can't have BW, WB, BR, or RB either, a contradiction. So there must not be any RWR or its permutations anywhere in the string.

Suppose card 1 goes to R, and card 2 goes to W. Card 3 can go to:
1. R, forming RWR, contradiction
2. W, forming a WW, contradiction
3. B.

So we have RWB as the beginning of the string. Now card 4 can go to:
1. R
2. W, forming a WBW, contradiction
3. B, forming a WBB, contradiction.
So card 4 must go to R.

We can continue this argument inductively to arrive that the entire string must have the form: RWBRWBRWB....