Maths Olympiad Prep

Library / /34 of 106

Combinatorics Difficulty 8.1 Shortlist Find the answer

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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Given the problem, let's denote the three boxes as R R (red), W W (white), and B B (blue). Each box must contain at least one card, and the numbers on the cards range from 1 to 100. The magician must be able to determine the box from which no card has been drawn using only the sum of the numbers on the two drawn cards.

To ensure the success of this trick, the sum of the numbers from two different boxes must uniquely determine the third box that has not been selected. This means that the sums from each pair of boxes should not overlap.

### Strategy:

1. Step 1: Partitioning the sum range.
- The minimum possible sum is 3=1+2 3 = 1+2 (when we draw cards numbered 1 and 2 from two different boxes).
- The maximum possible sum is 199=99+100 199 = 99+100 (when we draw cards numbered 99 and 100).
- We need to partition this range of sums among the three pairs of boxes (R,WR, W, W,BW, B, B,RB, R) such that each pair has its own distinct range of sums.

2. Step 2: Non-overlapping ranges for sums.
- This trick works if we can arrange the cards in these boxes such that no two sums coming from different pairs of boxes are equal.
- Assume S(R,W) S(R, W) , S(W,B) S(W, B) , and S(B,R) S(B, R) denote the set of possible sums from drawing one card from each of the corresponding boxes.
- These sets S(R,W),S(W,B),S(B,R) S(R, W), S(W, B), S(B, R) should be mutually exclusive.

3. Step 3: Building the ranges.
- Distribute numbers such that:
- One box gets the lowest range, say numbers 1 1 to x x .
- Another box gets the middle range.
- The last gets the highest range.
- Consider partitioning number 1 1 to 100 100 as 1 1 to a a , a+1 a+1 to b b , and b+1 b+1 to 100 100 for the three boxes.

4. Step 4: Approximating chosen boundaries.
- Ensure each partition [1,a] \left[1, a\right] , [a+1,b] \left[a+1, b\right] , [b+1,100] \left[b+1, 100\right] allows non-overlapping sum ranges when cards are drawn from different partitions.
- With each range having different minimum and maximum sum potential, deduce boundaries by integer checks and sum intersections to guarantee unique uncovered sums.

Through the process above, the following configuration emerges:

- Placing numbers to ensure partition integrity:
- Box distributions that allow only 12 overlapping-free allocations are naturally deduced when solving these overlaps by careful trial.

The distinct count where allocation is safest:
12 \boxed{12}
Thus, there are 12 distinct ways to arrange these partitions to sustain the magic trick, achieving complete non-overlapping sum results for the remaining unchosen box.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.