John's Red and Blue Balls

The main idea is to find the all probabilities that after $2$ hours the box contains exactly $77$ blue balls but the balls are added in a specific order (for example the blue balls first and then the red ones). Adding all this probabilities we can find the requested probability.

For example, the probability that the first two balls added are blue and the next three are red is: $\frac{1}{2} \cdot \frac{2}{3} \cdot \frac{1}{4} \cdot \frac{2}{5} \cdot \frac{3}{6}$ This is because the probability of taking out a blue ball at first is $\frac{1}{2}$ . The probability of taking out a blue ball after that the fist blue is added is $\frac{2}{3}$ . The probability of taking out a red ball after that the first two are added is $\frac{1}{4}$ ... and so on. Multiplying all this probabilities gives the requested probability.

After that $120$ balls are added, in any possible sequence, if we write the product of the probabilities for each step as before we note that the denominator is the product of all the numbers from $2$ to $121$ . In fact it increases by $1$ after each step (because one ball is added every time). Therefore the denominator must be $121!$ . If the blue balls added are $76$ and the red ones are $44$ the numerator must be $76!\cdot 44!$ because every time we add a blue ball it means that we have previously taken out (randomly chosen) a blue, and the probability of taking out a blue is a fraction with the number of blue balls in the box as the numerator. The same holds for the red balls.

Therefore the probability of each possible sequence in which the blue balls added are $76$ and the red ones are $44$ is: $\frac{76!\cdot 44!}{121!}$ all the sequences in which we can draw $76$ blue balls and $44$ red ones are: $120\choose 76$

Therefore adding all the probabilities gives: $\frac{76!\cdot 44!}{121!} \cdot {120\choose 76} =$ $\frac{76!\cdot 44!}{121!} \cdot \frac{120!}{76!\cdot 44!} =\frac{1}{121}$ Therefore the answer is: $\fbox{122}$

Define the function $P(n,x)$ as the probability that, after n minutes, there will be exactly $x$ blue balls in the box. Since there are 120 minutes in two hours, the question is asking us to find $P(120,77)$ .

We will use induction on $n$ to prove that, for a given $n\ge 0$ , $P(n,x)=\frac{1}{n+1}$ for all $1 \le x \le n+1$ .

Base Case: $n=0$

At the zero-minute mark, the only possible number of blue balls is 1. Therefore $P(0,1)=1=\frac{1}{0+1}$ .

Inductive Step:

Assume that for a given $k\ge 0$ , $P(k,x)=\frac{1}{k+1}$ for all $1\le x \le k+1$ . We want to show that $P(k+1,x)=\frac{1}{k+2}$ for all $1\le x \le k+2$ .

$P(k+1,x)$ represents the probability that after $k+1$ minutes, exactly $x$ of the $k+3$ balls will be blue. This can happen in one of two ways:

1. After $k$ minutes, $x$ of the $k+2$ balls were blue. Then a red ball is chosen, keeping the number of blue balls at $x$ . The probability of this occurring is $P(k,x)\cdot \left(1-\frac{x}{k+2}\right)$ .
2. After $k$ minutes, $x-1$ of the $k+2$ balls were blue. Then a blue ball is chosen, adding an $x$ th blue ball to the box. The probability of this occurring is $P(k,x-1)\cdot\frac{x-1}{k+2}$ .

Since these two cases are mutually exclusive, we have

$P(k+1,x)=P(k,x)\cdot\left(1-\frac{x}{k+2}\right)+P(k,x-1)\cdot\frac{x-1}{k+2}$ .

We will consider three cases, keeping in mind that since the box originally contained one ball of each color, there will always be at least one ball of each color in the box. So therefore, for all $n\ge 0$ , we have $P(n,0)=P(n,n+2)=0$ .

Case 1: $x=1$

$\begin{aligned} P(k+1,x) &= P(k,1)\cdot\left(1-\frac{1}{k+2}\right)+P(k,0)\cdot\frac{1-1}{k+2} \\ &= \frac{1}{k+1}\cdot\frac{k+1}{k+2}+0 \cdot 0 \\ &= \frac{1}{k+2} \end{aligned}$

Case 2: $1 < x < k+2$

$\begin{aligned} P(k+1,x) &= P(k,x)\cdot\left(1-\frac{x}{k+2}\right)+P(k,x-1)\cdot\frac{x-1}{k+2} \\ &= \frac{1}{k+1}\cdot\left(1-\frac{x}{k+2}\right)+\frac{1}{k+1}\cdot\frac{x-1}{k+2} \\ &= \frac{1}{k+1}\left(1-\frac{x}{k+2}+\frac{x-1}{k+2}\right) \\ &= \frac{1}{k+1}\cdot\frac{k+1}{k+2} \\ &= \frac{1}{k+2} \end{aligned}$

Case 3: $x=k+2$

$\begin{aligned} P(k+1,k+2) &= P(k,k+2)\cdot\left(1-\frac{k+2}{k+2}\right)+P(k,k+1)\cdot\frac{k+1}{k+2} \\ &= 0 \cdot 0 + \frac{1}{k+1}\cdot\frac{k+1}{k+2} \\ &= \frac{1}{k+2} \end{aligned}$

In all three cases, $P(k+1,x)=\frac{1}{k+2}$ , so the inductive step is complete.

Therefore, for a given $n\ge 0$ , $P(n,x)=\frac{1}{n+1}$ for all $1 \le x \le n+1$ . This means that $P(120,77)=\frac{1}{121}$ , and the answer to the question is $1+121=122$ .

All 121 possible counts, from 1 red and 121 blue to 121 red and 1 blue, are equally likely.

One way to prove this is by computing the probability of each of the 120 choose 76 ways to draw 76 blue balls and 44 red balls. If the blue balls come first, the probability is (1/2)(2/3)(3/4)...(76/77)(1/78)(2/79)...(44/121) = 76! 44!/121!. Every other path has the same probability since the same factors appear in the numerator, just in a different order. 120!/(76! 44!) * 76!4!/121! = 120!/121! = 1/121.

One deeper explanation is that this system is called Polya's Urn Model. It models sampling from a Bernoulli random variable with a uniform prior, which is a Beta(1,1) distribution. After drawing b blue and r red balls, the updated distribution is a Beta(b+1,r+1) distribution, so there is a (b+1)/(b+r+2) chance that the next ball is blue. Instead of drawing the balls one by one, you can choose the probability of getting a blue ball uniformly within [0,1], and then draw 120 balls according to this probability. The probability that you get 76 blue balls is then $\int_0^1 {120 \choose 76} p^{76} (1-p)^{44} dp.$ Integrating by parts says this equals $\int_0^1 {120 \choose 77} p^{77} (1-p)^{43} dp=...= \int_0^1 p^{120} dp = 1/121.$

Let $P_{t,b}$ be the probability that out of $t$ total balls there are $b$ blue balls. After experimenting with the first few $t$ 's, we can see that $P_{t,b} = \frac {1}{t-1}$ . We now prove this by induction:

The base of our induction: $P_{2,b} = 1$ is obviously true since the box starts out with 2 balls and a fixed number of blue balls.

The induction step: Let us assume that

$P_{m,b} = \frac {1}{m-1}$

We can then deduce that

$P_{m+1,b} = P_{m,b} * (\frac {m-b}{m}) + P_{m,b-1} * (\frac {b-1}{m})$

$\quad \quad \quad = (\frac {1}{m-1})(\frac {m-b}{m}) + (\frac {1}{m-1})(\frac {b-1}{m})$

$\quad \quad \quad = \frac {m-b+b-1}{m(m-1)}$

$\quad \quad \quad = \frac {1}{m}$

It follows by induction, that $P_{t,b} = \frac {1}{t-1}$ is in fact true. Since after 2 hours there will be 122 balls, the question is asking for $P_{122,77} = \frac {1}{121}$ . Thus our answer is $1+121=122$ .

First, let's find the pattern and then, we'll show why it's general... I will use the notation [total balls: (number of blue balls, probability)] 2 total : (1,1) 3 total: (2,1/2) and (1,1/2) 4 total: (3,1/2 2/3) and (2, 1/2 1/3 + 1/2 2/3) and (1, 1/2 2/3) 4 total: (3, 1/3) and (2, 1/3) and (1, 1/3) 5 total: (4, 1/3 3/4) and (3, 1/3 1/4 + 1/3 1/2) and (2, 1/3 1/2 + 1/3 1/4) and (1, 3/4 1/3) 5 total: (4, 1/4) and (3, 1/4) and (2, 1/4) and (1, 1/4)

Hmm...it looks like the probability is evenly distributed. That's kind of exciting! How did it happen?

If you set up each total as a row, it will seem like each row relates to the one before in the exact same way as the previous row relates to the one before it. Any time something is repetitive like this, it is a good idea to check and see if there is an inductive proof hiding.

We know row 1 [total 2: (1,1)] is true, and it will be our base case. I believe that in row n [total n+1: (n,1/n) and (n-1, 1/n) and (n-2,1/n) and ...]

Ways to make n in row n is by adding 1 to the n-1 from previous row 1/n * (n/n+1) gives [total n+2: (n+1, 1/(n+1))]. Note that this is exactly what we want because it is [total n+1: (n, 1/n)] where n --> n+1.

Thus, it will work for every row after the first one. In the 121st row [total 122: (121, 1/121) and (120, 1/121) and ... (77, 1/121)

a = 1 b = 121 a+b = 122

After $2$ hours ( $120$ minutes) we have total $122$ balls in the box. There is at least a red ball or a blue ball.

Let $p(k,n)$ be the probability that there are $k$ blue balls in the box containing total $n$ balls after $n-2$ minutes.

At the time $n-2$ minutes, the box has exactly $k$ blue balls if a minutes ago, the box contained either $k-1$ blue balls and John took out a blue ball, put it back another one, or $k$ blue balls, then he put in a red one. It means that $p(k,n)$ depends on $p(k-1,n-1)$ and $p(k,n-1)$ .

Note that in the case the box has total $n-1$ ball and the number of blue balls is $k-1$ , the probability of taking out a blue ball is $\dfrac{k-1}{n-1}$ , and if the number of blue balls is k, the probability of taking out a red one is $\dfrac{n-1-k}{n-1}$ . We have the expression: $p(k,n) = p(k-1,n-1). \dfrac{k-1}{n-1} + p(k,n-1)\dfrac{n-1-k}{n-1}$

with the initial condition are $p(1,2) = 1, p(0,2) = p(2,2) = 0$ .

By this expression, we calculate that $p(76,122) = \dfrac{1}{121}$ . Therefore, $a+b=122.$

P(n) = probability of n blue balls after t minutes. t Probability for possible numbers of blue balls
1 P(2)=1/2 P(1)=1/2
2 P(3)=2/3 1/2=1/3 P(2)=1/3 1/2+1/3 1/2=1/3 P(1) =2/3 1/2=1/3 3 P(4)=3/4 1/3=1/4 P(3)=1/4 1/3+1/2 1/3=1/4
P(2)=1/2
1/3+1/4 1/3=1/4 P(1)=3/4 1/3=1/4 t P(n)=1/(t+1) , for n=[1,t]
120 P(120)=1/121…P(77)=1/121 …P(1)=1/121

Could use induction but pattern obviously continues so P(120) = a/b = 1/121 => a + b + 122.

let P(n,k) be the probability that n blue balls occur after k minutes . P(n,k) can be thought of as probability of choosing blue at kth minute with n-1 blue balls in bag or probability of choosing red at kth minute with n bluein bag .

P(n,k)=(n-1)/(k-1) P(n-1,k-1)+(k+1-n)/(k+1) P(n,k)

boundary condition P(1,0)=1 P(K!=1,0)=0 P(1,1)=1/2

Let $X_n$ be the random variable that represents the number of blue balls in the box after $n$ minutes. Since the box will always contain at least one blue ball and at least one red ball, we see that the only possible values for $X_n$ are $1,2,3,\dotsc,n+1$ .

${\bf Lemma.}$ For each integer $1\leq k\leq n+1$ , the probability that $X_n=k$ is equal to $\frac{1}{n+1}$ ; in other words, each of the possible values of $X_n$ is equally likely to occur.

Assuming the assertion of the lemma for the time being, we see that the probability that $X_{120}=77$ , which is the probability that the problem asks us to compute, is equal to $\frac{1}{121}$ . Hence the answer is $1+121=122$ . It remains to give a proof of the lemma.

We use induction on $n$ . The base case is $n=0$ . Here we know that $X_0=1$ by assumption (after $0$ minutes, nothing happened yet, so the box contains exactly one blue ball), and the lemma asserts that the probability that $X_0=1$ is equal to $\frac{1}{0+1}=1$ , which is true.

For the induction step, assume that the lemma is true for some integer $n\geq 0$ . Choose an integer $1\leq k\leq n+2$ . Let us calculate the probability that $X_{n+1}=k$ . By assumption, John's box will contain $k$ blue balls after $n+1$ minutes in one of the following mutually exclusive cases.

Case 1: the box contained $k$ blue balls after $n$ minutes, and John took out a red ball during the $(n+1)$ -st minute.

Case 2: the box contained $k-1$ blue balls after $n$ minutes, and John took out a blue ball during the $(n+1)$ -st minute.

The probability of Case 1 occurring is equal to the product of the probability that $X_n=k$ and the probability that a randomly chosen ball, from a box that contains $k$ blue balls and $n+2-k$ red balls, is red. So the probability of Case 1 equals $\frac{n+2-k}{n+2}$ times the probability that $X_n=k$ . Similarly, the probability of Case 2 equals $\frac{k-1}{n+2}$ times the probability that $X_n=k-1$ . Applying the induction hypothesis shows that the probability that $X_{n+1}=k$ is equal to the sum $\frac{1}{n+1}\cdot\frac{n+2-k}{n+2}+\frac{1}{n+1}\cdot\frac{k-1}{n+2} = \frac{1}{n+1}\cdot\frac{n+1}{n+2}=\frac{1}{n+2},$ which completes the induction step.

${\bf Remark.}$ The careful reader will notice that in the induction step of the proof above, one should separately consider the cases where $k=1$ (because then the probability of $X_n=k-1$ is $0$ ) and where $k=n+2$ (because then the probability of $X_n=k$ is $0$ ). However, an easy inspection shows that the formula for the probability of $X_{n+1}=k$ that we derived is also valid in these two cases (since the relevant case 1 / case 2 will have probability 0).