6
$\begingroup$

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$
  • $\begingroup$ As others have stated, you are correct that the solution your propose leads to a $149/199\approx .749$ probability. However, this does not prove that this solution is optimal, i.e. better than any other configurations with $i$ white and $j$ black marbles in the first urn ($0\leq(i,j)\leq100$) --- a total of $101^2$ possibilities. Intuition (?) is that the solution is indeed optimal, as does exploration with numerical software (or even spreadsheet). There may be another way to prove optimality... $\endgroup$ – A.G. Nov 20 '16 at 19:25
  • $\begingroup$ @A.G. what? Algebra and differentiation can prove it. No need for exploration with numerical software. $\endgroup$ – smci Nov 20 '16 at 21:38
  • 2
    $\begingroup$ It occurs to me that the selection process is not necessarily "purely random." How large are the urns? How many marbles can exist side-by-side on the "bottom layer" before new marbles start forming a second layer? If the urns were small enough, I would dump all black marbles in one, and then dump 99 white marbles on top of the blacks to form a "thick protective layer." On the theory that if the King picks that urn, he'll probably be lazy, and grab one near the top, instead of digging very deep. If I put the last white in Urn #2, there's a 50-50 chance that he picks that urn, and I win. $\endgroup$ – Lorendiac Nov 20 '16 at 23:24
  • 12
    $\begingroup$ Everyone is wrong. The correct solution is not to put any of the black marbles in either urn. $\endgroup$ – Derek Elkins left SE Nov 21 '16 at 0:31
  • 2
    $\begingroup$ @Lorendiac the problem should probably specify that the king instructs you to put each marble in one of the urns. $\endgroup$ – stewbasic Nov 21 '16 at 5:35
4
$\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 enter image description here

Interestingly $$\lim_{n\to\infty}\max_{n_w,n_b}P(S)=\frac{3}{4}$$

| cite | improve this answer | |
$\endgroup$
17
$\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$.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

It is obviously a mistake because the $\frac {99}{200} $ would imply there are 101 black marbles.

You are right.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

The app is wrong and you are correct. Good work.

| cite | improve this answer | |
$\endgroup$
  • 9
    $\begingroup$ I believe it does. OP asked if s/he was correct and gave a good explanation of his/her logic. $\endgroup$ – Ross Millikan Nov 20 '16 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.