Math Brainteaser: The Prisoner’s Last Wish
Level of Difficulty: Highschool
A prisoner is sentenced to death. Before being executed, the king announces that he will give the prisoner one last chance to save his skin. He gives him 100 balls, 50 of which are black and 50 of which are white, and two identical urns. He then asks the prisoner to distribute the balls as he sees fit between the two urns. “The idea,” explains the king, “is simple. Once you’ve distributed the balls, I’ll rearrange the urns at random so you won’t know which is which. Then I’ll let you pick an urn, and then I’ll have you reach in and take a ball out at random. If you’ll take out a white ball, I’ll spare your life.”
What would be the prisoner’s best strategy?
EDITED, 28/June/2009: just to make things clear, I’d like to reiterate that once the balls are distributed among the two urns, the urns are shaken. The choice of urn, as well as the choice of ball from within the selected urn, are uniformly random.
EDITED, 29/June/2009: hats off to our reader,
My father offers the following solution: Place all 50 black balls in Urn A, and then drop 49 of the white balls on top of the black balls in Urn A. Place the remaining white ball in Urn B. This way, if Urn A is selected, the chance of being spared is higher than 49/99 because all the white balls are on top. So the probability of surviving will be no less than 148/198.
I’m probably to blame for not wording the problem correctly, but I meant for it to be a totally random deal. Once the balls are distributed among the two urns, the urns are shaken. The choice of urn, as well as the choice of ball from within the selected urn, are uniformly random.
His best strategy is placing one white ball in one urn and the remainding black and white balls in the other urn. With this strategy, the probability of living is 1/2 * (1+ 49/99) \approx 0.747.
True! This can also be shown rigorously, but I’m going to stick with your intuitive answer.
This puzzle was originally presented by Sam Loyd (1841-1911), perhaps the 19th century’s most prominent recreational mathematician. Even the great Martin Gardner honored him by calling him “America’s greatest puzzlist” in the introduction to his book, “Mathematical Puzzles of Sam Loyd”:
http://www.amazon.com/gp/product/0486204987?ie=UTF8&tag=physicincorr-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0486204987
Sam Loyd probably has more puzzles ascribed to him than any other recreational mathematician, Gardner excluded.
I actually solved by solving the optimization problem
argmax 1/2 * (a/(100-b) + (50-a)/b) subject to the constrains
a \in Integers intersected with [0,50]
b \in Naturals intersected with [1,100]
I know I’m coming late to the party, but one of my teachers in grade 4 or 5 actually presented our class with this problem. I remember thinking it was awfully clever…