# Is there a clever solution to this elementary probability/combinatorics problem?

My friend was asked the following problem in an interview a while back, and it has a nice answer, leading me to believe that there is an equally nice solution.

Suppose that there are 42 bags, labeled $0$ though $41$. Bag $i$ contains $i$ red balls and $42-(i+1)$ blue balls. Suppose that you pick a bag, then pull out three balls without replacement. What is the probability that all 3 balls are the same color?

The problem can be solved easily by using some basic identities with binomial coefficients, and the answer is $1/2$. Moreover, if $42$ is replaced by $n$, the answer does not change, assuming $n>3$. However, this computational approach obscures any hidden structure there might be. Ideally, I would like a simple and direct proof that the probability of getting RRR is the same as the probability of getting RBB.

So, is there a nice solution to the problem, one that could be explained fully to someone without the use of paper? Or is there no good way to explain this beyond computational coincidence?

-

The game can be reformulated in the following way: There is one urn with 42 balls numbered 0 through 41. You start by drawing and keeping one ball (this corresponds to picking a bag in your version). The urn is then taken away while an assistant paints all balls with a lower number than your first draw red and the rest of them blue. Then you draw three more balls and see whether they have the same color.

Now, this is equivalent to first drawing four of the numbered balls, then among those four pick a random one to be the "bag" ball and coloring the other three according to that choice. But doing it that way, we can see that the initial drawing of four balls is entirely superfluous -- only the order relation between them matters, and any ordered set of four balls have the same structure. So we might as well forgo the initial draw and just start out with four balls numbered 1, 2, 3, and 4. Then you win if the one you pick in the second draw is either 1 or 4, and the probability of that is, naturally, 1/2.

-
+1 -- very nice :-) This also immediately yields the generalized version that the probability for $k$ balls is $2/(k+1)$. – joriki Oct 8 '11 at 2:27
Thanks. That's quite a beautiful solution. – Aaron Oct 8 '11 at 2:41
I like this solution (+1). I came up with the same solution looking at this problem in the same way as one looks at the problem "how many ways can $n$ identical balls be put into $m$ urns" where each arrangement of balls and urns can be mapped to a unique arrangement of $n\bigcirc$s and $(m{-}1)\;\vert$s. I mapped each bag to $41\bigcirc$s and $1\;\vert$ to denote "red to the left" and "blue to the right". Then replacing $3\bigcirc$s with $\bigotimes$s, I realized that the remaining $\bigcirc$s were superfluous and I only needed to look at the arrangement of the $3\bigotimes$s and $1\;\vert$. – robjohn Oct 8 '11 at 13:59
So now we can ask: Given $55$ bags, each with $9$ marbles in every possible combination of red, green, and blue. What is the probability that, choosing $3$ marbles at random from a random bag, all $3$ are of the same color? – robjohn Oct 8 '11 at 14:19

While I really like Henning Makholm's solution, it also might be interesting to see a bijection from the RRR outcomes to the RRB outcomes to the RBB outcomes to the BBB outcomes. The bijection doesn't depend on the number of balls chosen (e.g., the process gives RRRR to RRRB to RRBB to RBBB to BBBB in the case of four balls), and so it shows that if we choose $k$ balls rather than $3$ from each bag, the probability of all $k$ balls being the same color is $\frac{2}{k+1}$.

For bag $i$, number the red balls $1$ through $i$ and the blue balls $1$ through $n-(i+1)$. Then, for any outcome in any bag, draw an X on the three balls chosen. For an RRR outcome, take the highest-numbered red ball with an X, paint it (retain the X) and all higher-numbered red balls blue, and renumber them so that they are now the highest-numbered blue balls, preserving the internal ordering of the balls switched. Finally, change the label on the bag to account for the new number of red balls. This gives a mapping from the set of RRR outcomes to the set of RRB outcomes. Moreover, the mapping is reversible, since for any RRB outcome you can take the blue ball with an X, paint it and all higher-numbered blue balls red, renumber them so that they are now the highest-numbered red balls, and change the label on the bag to account for the new number of red balls. So we have a bijection between the set of RRR outcomes and the set of RRB outcomes.

You can then apply this process again for any RRB outcome, painting the highest-numbered red ball with an X and and all higher-numbered red balls blue. This gives a bijection between the RRB outcomes and the RBB outcomes. Applied again gives a bijection between the RBB outcomes and the BBB outcomes. Thus these four sets are the same size, and so the probability that we obtain an RRR or BBB outcome is $\frac{1}{2}$.

-
(I think there's a missing step. If you paint some balls in only one bag, you make its new distribution equal to that of some other bag. To biject onto the originally-possible outcomes, you have to also do the opposite painting for balls in that other bag and swap the two bag numbers. This step shows the importance of starting with one bag of each possible distribution---if you didn't, you might not be able to bijectively swap bag numbers as needed.) – krubo Oct 8 '11 at 12:27
@krubo: I thought the bijection being from an outcome in one bag to an outcome in a different bag was implicit in my answer, but I can certainly make it explicit. – Mike Spivey Oct 8 '11 at 14:02