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?

Solution 1:

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.

Solution 2:

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}$.