Puzzles, Maths and Algorithms: Math Magician
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, such that each box contains atleast one card. A member of audience draws two cards from two different boxes and announces the sum of the number on those cards. Given this information magician locates the box from which no card has been drawn. How many ways are there to put the cards in the boxes so that the trick works.Source: International Maths Olympiad 2000
Answer: 12
Solution:
We split the possible arrangements into two different cases.
Case 1: Assume that there exists an i such that i, i+1, i+2 go in different box (say wrb). Since, (i+1) + (i+2) = i + (i+3) => (i+3) should go in white box. Similarly i-1 should go in blue box. Since the pattern repeats without much choice so it boils down to assigning different boxes to first three cards. Total of 6 ways.
Case 2: Assume that no three neighbors are put in different boxes. Let card 1 be in white box. Let i be the smallest card to go in red box (such that i > 2). Let j be the smallest card to go in blue box (such that j < 100). Let j > i.
==> i-1 is in white box.
==> i + j = (i-1) + (j+1)
==> j+1 is in white box.
==> i + (j+1) = (i+1) + j
==> i+1 is in blue box
==> j = i+1
This violates the main assumption from both ends i-1, i, i+1 are in different boxes and also i, i+1, i+2, hence j = 100. so that j+1 doesn't exist and both 99 and 98 belong to same box other than blue.
also (i-1) + 100 = i + 99 => card 99 is in red box => card 98 is in red box
but 2 + 99 = 1 + 100 => 2 is red. in general assume that there exists a card c (>1) and it belongs to white box and also c-1 to white box. => c + 99 = (c-1) + 100. which leads to failure of the trick. Assuming cards surrounding c are red. c + 99 = c-1 + 100 => failure of trick. Hence no such c exists and c=1 is the only card in white box.
hence the combination looks like wrrrr.........rrrrrb i.e. one card (value 1) in white box, one card (value 100) in blue box and rest all cards in red box. There are six ways of such arrangements.
Read full article from Puzzles, Maths and Algorithms: Math Magician
