Statistics brainteaser: marbles in two bags

Here’s an interesting brainteaser I found. Suppose you are given red marbles and blue marbles, as well as two bags. You may place any combination of marbles in both bags. After you are done placing the marbles, I will select a bag at random, and select a marble at random from within that bag. Maximize the probability of drawing a red marble by distributing the marbles appropriately.

I challenge you to solve this by brute force! Write down the probability function, take first order conditions, realize that this is an integer programming problem, scratch your head…

That was actually my first attempt. I quickly found out that reasoning is much easier. Read on for my solution after solving it yourself of course! (By the way, it is fairly easy to come up with the correct answer. Can you prove that it is correct?)

First, it’s easy to see that you can do better than simply putting equal allocations in both bags, or by leaving one of the bags empty. For example, by putting a single red marble in the first bag, and the rest of the marbles in the second bag, the probability of choosing a red marble exceeds one half. Since the equal allocation and the equal-empty allocation are clearly not the best allocations, the best allocation must have a different ratio of red marbles to blue marbles in each bag. Since “first” and “second” bag are arbitrary labels, let’s suppose that the first bag contains more red marbles than blue marbles.

If the first bag contains no blue marbles, then the first bag contains only red marbles. If it contains only red marbles, then we can clearly improve the allocation by moving all but one red marble to the other bag. Thus, the optimal allocation cannot contain more than one red marble and no blue marbles in the first bag.

If the first bag contains at least one blue marble, then we can improve the ratio of red marbles to blue marbles by removing one red marble and removing one blue marble because we assumed the first bag has more red marbles than blue marbles (this is a simple arithmetic result that I’m not proving: if then ). The second bag has fewer red marbles than blue marbles because the first bag has more red marbles than blue marbles. Thus, adding a red marble and a blue marble will increase the ratio of red marbles to blue marbles in the second bag (this is the same inequality discussed in the previous parenthetical remark). Since doing this transfer improves the probability of choosing a red marble, no allocation with any blue marbles in the first bag can be optimal.

Putting this all together, we have shown that in the optimal allocation, one of the bags must be nonempty and have more red marbles than blue marbles; that this bag cannot contain any blue marbles; and moreover, that this bag can contain at most one red marble. Thus, the optimal allocation is one red marble in one of the bags, and the rest of the marbles in the other bag.

What do you think? Do you have an easier solution?