Solution #6

First we specify 12 arrangements that work, and then we prove that these are the only arrangements that work.

Suppose all of the numbers that are 0 mod 3 are put in one box, all of the numbers that are 1 mod 3 are put in another box, and all of the numbers that are 2 mod 3 are put in the third box. Then when two numbers are drawn from two boxes, their sum mod 3 determines their origin.

If their sum is 0 mod 3, they came from the 1 mod 3 and the 2 mod 3 box. If their sum is 1 mod 3, they came from the 0 mod 3 and the 1 mod 3 box. If their sum is 2 mod 3, they came from the 0 mod 3 and the 2 mod 3 box.

This is then sufficient for the magician to determine the unused box. But there are six ways for the magician to distribute the numbers in this way, since there are three ways to choose the box into which to put the 0 mod 3 numbers, and then 2 ways to choose the box into which to put the 1 mod 3 numbers.

Suppose instead that 1 is put into one box, 2 - 99 are put in a second box, and 100 is put in the third box.

Then if the sum is 3 - 100, the first two boxes were chosen. If it is 101, the first and third box were chosen. If it is 102-199, the second and third boxes were chosen.

Again, this is sufficient for the magician to determine the unused box. And again there are six ways of achieving this arrangement, for a total of 12.

We must now prove that these 12 are the only workable arrangements. We will in fact prove that this is true for any number n of numbers, assuming n is at least 4. We do this by induction on n.

We begin with the case n = 4. There are (ignoring the selection of box color) only six ways to arrange {1,2,3,4} into the three boxes:

{1},{2},{3,4}
{1},{2,3},{4}
{1},{2,4}{3}
{1,2},{3},{4}
{1,3},{2},{4}
{1,4},{2},{3}

Checking each case, we find that only the second and the sixth work, which fits our claim.

We now assume that only our specified arrangements work for n, and consider n+1.

We separate two cases: the number n+1 is in a box by itself, or it is not.

Suppose n+1 is in a box by itself. Now suppose that n and k are in different boxes, for some k > 1. Then n+k can be formed by selecting them. But n+k can also be formed by selecting n+1 and k-1, and these will come from different boxes than n and k (since n+1 is by itself). Thus 2 through n must be in the same box, which means 1 is in a box by itself. This is the arrangement that has 1 in a box, the largest number in a box, and all the other numbers together in a single box.

Now suppose n+1 is not in a box by itself. Then if n+1 is removed, we have a permissible arrangement of 1 through n. This arrangement must either be by remainder mod 3, or the smallest-largest-other arrangement.

If it is by mod 3, n+1 must go in the box matching its mod 3. If it does not, then it is in a different box from n-2, and the sum 2n-1 can be made by adding the two of these. But n and n-1 are in different boxes, and also sum to 2n-1, which is impermissible.

If it is by smallest-largest-other, then n+1 cannot be put anywhere. If it is put with 1, it can be added to 2 to form n+3. But n is in a box by itself, and can be added to 3 to make n+3. If it is put with n or with {2,...,n-1}, it can be added to 1 to form n+2, and n can be added to 2 to form n+2.

Thus in both cases, we have to preserve one of our permissible arrangements, showing that these are the only permissible arrangements. This shows that 12 is the maximal number (and, in fact, is the maximal number for any n greater than or equal to 4).