I've tried searching for this question but couldn't find it on stackexchange. This is a common type of interview question; I ran into it doing brain teasers on a probability puzzles app, and if you fine people agree with my logic, I will inform the app developer that his/her answers are incorrect.
The problem is essentially this:
You are sentenced to death for thievery. The King is magnanimous and decides to put your fate in the hands of chance. You are given $100$ white marbles and 100 black marbles, and $2$ urns. The king will choose an urn at random and pull out a single marble at random; if the marble is white, you live, if its black, you die. If you place the marbles in the best way possible, what is your probability of survival?
I started with the base case: $100$ white marbles in one urn, $100$ black marbles in the other. This comes down to a $50$-$50$ chance of survival. I then worked my way to deciding that placing $1$ white marble in one urn and $99$ white marbles + $100$ black marbles in the other urn would be the "best way possible", which yields the following:
$$P(\text{Survival}) = \frac{1}{2}(1+\frac{99}{199}) \approx .749$$
Selecting $1$ of $2$ urns at random gives $\frac{1}{2}$, the urn containing $1$ marble gives $1$, and the other that contains $99$ white marbles and $100$ black marbles gives $\frac{99}{199}$ because there are $99$ possible white marbles to select out of $199$ total marbles.
The app claims that the correct answer is $\frac{1}{2}(1+\frac{99}{200}) \approx .748$
I see where the $200$ comes from, but I do not think it is right to say that there are $200$ marbles in the other urn. Who is correct?
$\endgroup$ 74 Answers
$\begingroup$If you want a proof that your solution is optimal, consider the following:
Clearly, if you put an equal number of black balls and white balls in each urn, the probability of survival is $\frac{1}{2}$.
Thus, in the optimal solution, one of the urns will have more white balls, and the other will have more black balls. The urn with more white balls can't give you a chance of survival of more than $1$, and the urn with more black balls can't give you a chance of survival of more than $99/199$.
$\endgroup$ 0 $\begingroup$It is obviously a mistake because the $\frac {99}{200} $ would imply there are 101 black marbles.
You are right.
$\endgroup$ $\begingroup$To be even more precise with the proof one can use the law of total probability to define the probability of survival as follows $$P(S)=P(U_1)P(S|U_1)+P(U_2)P(S|U_2)$$ where $U_1,U_2$ - events of the respective urn being picked by the king and $S$ - the event of survival.
The above translates into $$P(S) = q\frac{n_w}{n_w + n_b} + (1 - q)\frac{n - n_w}{2n - n_w - n_b},$$ where $q=\frac{1}{2}$ - the probability of the king picking the first urn; $n_w, n_b = 0,\ldots,n$ - number of white and black marbles in the first urn respectively and $n = 100$ - total number of marbles of each colour.
Maximizing for $n_w$ and $n_b$ gives $$\max_{n_w,n_b}P(S)|_{n=100}=\frac{149}{199}\approx0.7487$$ for either $n_w=1,n_b=0$ or $n_w=n-1,n_b=n$ since the problem is symmetrical.
3D plot of $P(S)|_{n=100}$ with the maxima in the top left and top right corners
Interestingly $$\lim_{n\to\infty}\max_{n_w,n_b}P(S)=\frac{3}{4}$$
$\endgroup$ $\begingroup$The app is wrong and you are correct. Good work.
$\endgroup$ 1
