Smash this puzzle by using a smarter way of revealing the randomness!
Imagine there are n=100
bins numbered 0,1,2,…,99
. The bin number k
contains k
red balls and 99-k
blue balls.
You choose one bin at random and pick one ball at random from it. You look at the ball and it is red. You pick another ball from the same bin, without replacing the first ball. What is the chance of getting another red?
Or even more generally, you pick x
balls (0<=x<=98
) and all of them are red. What is the chance that the next one is also red?
1. Edge cases
Conditional probability is a straightforward way of solving these kinds of problems. But if you start using it, soon you will realize how fast it gets complicated. There are 3
edge cases that are still easy to solve, and can help us build a hypothesis.
- Edge case
x=0
: By symmetry, the chance is1/2
, that’s it. - Edge case
x=1
(the original question): This question is not so easy for the generaln
. But if you modify the question and usen=3
instead ofn=100
, it is doable. The answer will be2/3
, which is the same asn=100
- Edge case
x=98
: On the other side of the spectrum, forx=98
the problem is also easy. As we will discuss the answer is99/100
.
So, apparently for general x, the answer is (x+1)/(x+2). And as always, in this kind of situation, we expect to see a brilliant solution giving a sharp reason why this is always the case. And this is what this post is about.
A. Edge case x=0
This is the easiest case. When x=0
, it means that we don’t have any information about the bin that we have picked. So, the chance of having a red ball is simply the number of red balls over the total number of balls, which is 4950/9900=1/2
. This is true, regardless of the distribution of the red balls in the bins.
B. Edge case x=1 (for n=3)
In this case, you have only 3
bins.
- Bin
0
with2
blue balls - Bin
1
with1
blue ball and1
red ball - Bin
2
with2
red balls
We know that the first ball was red. So, we are not in the bin 0
for sure. We are either in bin 1
or bin 2
. But are these events equally likely? No! The chance of being in bin 2
is twice than being in bin 1
. So, the chance of being in bin 1
is 1/3
and being bin 2
is 2/3
. (You need to apply the Bayes theorem if you want rigorous proof for it.)
So, the chance for the second ball to be red is (1/3)*0 + (2/3)*1 = 2/3
C. Edge case x=98
This is also similar to the previous case. So, imagine you have picked 98
balls and all of them were red so far. Therefore, we are left with only two possibilities regarding the bins. Either we are in the bin 98
or the bin 99
as the bin contained at least 98
red balls. And we can expect that the chance of being in bin 99
is much higher than bin 98
. Skipping the details of the Bayes theorem, the chance of being in bin 99
should be 99
times than the bin 98
. Why? Because the chance of picking all of the 98
red balls of bin 98
is (98/99)*(97/98)*...*(1/2) = 1/99
while the chance of picking 98
red balls from bin 99
is simply 1
.
So, the chance of being in bin 98
is 1/100
and the chance of being in bin 99
is 99/100
. Therefore, the chance for the last ball to be red is (99/100)*1 + (1/100)*0 = 99/100
.
2. The proof
Reading the edge cases above, you might be tempted to believe that the other cases should be also easy to solve with the same ideas. But this is not the case. To have a general proof, we need to think differently. As the first step, we are going to reformulate the question.
A. Analysis
The game in puzzle has three steps:
- A bin is chosen at random. (We don’t know which one)
- A ball is chosen at random from the bin. (We know it is red)
- Another ball is chosen from the ball. (We want to know its color)
Having these steps in mind, we can reformulate the question to make it easier to solve.
B. Reformulation (case x=1)
Consider this variant of the question:
Imagine we have 1
(and not n=100
) bin with 100
(and not 99
) balls in it. All of the balls are white and the numbers 1,2,...,100
are carved on them. We, together with three friends, are waiting outside the room, talking about what we are going to do.
- The first friend enters the room, picks
1
ball from the100
balls in the bin and paints all of the balls with a lower number than that, as red and the rest as blue. He drops the ball into a jar and leaves the room. - The second friend enters the room, picks another ball from the bin and shouts loudly, “IT IS RED!”. He also drops the ball into the jar and leaves the room.
- The third friend enters the room, picks another ball and drops the ball into the jar, and leaves.
Now it is our turn to go to the room. But, just before going to the room, due to an accident, we lose our sight and become blind (or at least color-blind). Despite the unfortunate accident, we don’t give up and enter the room, find the jar, and try to calculate the probability that the ball that our third friend picked was red.
C. Solution
All we find is a jar with 3
balls with 3
numbers carved on them. A big number (B), a medium number (M), and a small number (S)! Based on this information, which is the same as the information in the original question, we want to calculate the probability. There are 6
possible ways of ordering these 3
numbers.
- B → M → S: This means that the first friend took the largest number. The second one took the medium number (which was red since it was smaller than the first ball) and the third friend took the smallest number. In this case, it is red too. So call this scenario a success.
- B → S → M: This case is similar to the previous one. The first ball is the biggest, so the other two balls are red. This scenario is also a
SUCCESS
. - M → S → B: This case is different. The first friend took the medium ball. The second friend took the smallest ball, which was red since the first friend had painted it to be so. But the third ball is painted blue since it is bigger than the first ball. So, this scenario is a
FAILURE
. - M → B → S: If you think about it, this scenario could not have happened. Why? Because we know that the second ball was red. In this scenario, the second ball is bigger than the first ball. So, according to the plan it should have been blue. We call this scenario
INVALID
. - S → M → B: This scenario also could not have happened. The second ball cannot be bigger than the first ball.
INVALID
- S → B → M: With the same argument, this is also
INVALID
.
So, in the end, among 3
valid scenarios, 2
of them were a success. Since all of the valid scenarios are equally likely, the chance of success is 2/3
!
D. Solution to the general case
The argument is easy to generalize for general x
. In this case, your second friend picks x
balls from the bin and shouts “ALL WERE RED!”
Then, in the end, there are x+2
balls in the jar. So, there are (x+2)!
possible ordering for them. However, most of these cases are INVALID
since we know that the first ball is bigger than every other ball, except possibly for the last one. There are two types of valid scenarios:
Type 1. Biggest → Everything else: Contains (x+1)!
cases, all are SUCCESS
Type 2. Second biggest → Everything else → Biggest: Contains x!
cases, all are FAILURE
.
Every other scenario is INVALID
, since the balls in between should have been all red. So, the chance of success is (x+1)!/[(x+1)!+x!]=(x+1)/(x+2)
.
And that was it! Imagine if you wanted to solve this, using conditional probability! It would be a nightmare!
3. Condolences
I know the solution seems like magic to you. But I would like to remind you that you have unconsciously used this method previously. Where?
How do you solve these questions?
- Picking two distinct numbers in
1,2,3,...,100
, what is the chance that the first one is bigger? - Picking three distinct numbers in
1,2,3,...,100
, what is the chance that the first one is the biggest? - Picking three distinct numbers in
1,2,3,...,100
, and knowing that the last one is the smallest number, what is the chance that the first one is the biggest?
The answer to the first one is 1/2
, but how did you find it? Did you say there are only two scenarios S → B and B → S from which one is SUCCESS and one is FAILURE
? Or did you partition on the 100
possible outcomes of the first ball and calculate the chance for the second ball to be lower than that?
I bet you didn’t make it that hard for yourself. The same goes for this problem. Don’t make it hard!