IMO 2000 SL C1

Origin: HUN | Category: Combinatorics

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 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

In order for the trick to work, whenever x + y = z + t and the cards x, y are placed in different boxes, either z, t are in these boxes as well or they are both in the remaining box. Case 1. The cards i, i + 1, i + 2 are in different boxes for some i. Since i+ (i+ 3) = (i+ 1)+ (i+ 2), the cards i and i+ 3 must be in the same box; moreover, i −1 must be in the same box as i + 2, etc. Hence the cards 1, 4, 7, . . ., 100 are placed in one box, the cards 2, 5, . . ., 98 are in the second, while 3, 6, . . . , 99 are in the third box. The number of different arrangements of the cards is 6 in this case. Case 2. No three successive cards are all placed in different boxes. Suppose that 1 is in the blue box, and denote by w and r the smallest numbers on cards lying in the white and red boxes; assume w.l.o.g. that w < r. The card w + 1 is obviously not red, from which it follows that r > w+1. Now suppose that r < 100. Since w+r = (w−1)+(r+1), r+1 must be in the blue box. But then (r + 1) + w = r + (w + 1) implies that w + 1 must be red, which is a contradiction. Hence the red box contains only the card 100. Since 99 + w = 100 + (w −1), we deduce that the card 99 is in the white box. Moreover, if any of the cards k, 2 \leqk \leq99, were in the blue box, then since k + 99 = (k −1) + 100, the card k −1 should be in the red box, which is impossible. Hence the blue box contains only the card 1, whereas the cards 2, 3, . . . , 99 are all in the white box. In general, one box contains 1, another box only 100, while the re- maining contains all the other cards. There are exactly 6 such ar- rangements, and the trick works in each of them. Therefore the answer is 12.