Reach for the Sky


Reach for the Sky!

Reach for the Sky! is based on hollow lottery balls. Here is how it is played.

Your adversary is given 100 identical pieces of paper. In a room hidden from your view, he writes a number on each one - he can choose any value in the range 1 to 1 million but without duplicates - then inserts them into small opaque envelopes. Subsequently, these papers are given to an independent third party called the “stuffer.” The stuffer works in full view of you and your adversary at all times. He shows you 100 hollow and empty lottery balls. He then shuffles the envelopes and inserts one envelope into the first lottery ball, another into the second, and so on up to 100. After inserting each envelope, he screws the ball shut. These balls have been examined using drop tests, bounce tests, and resilio-metric tests to be sure they all share the same physical properties.

The stuffer then puts the balls into a lottery machine. The lottery machine mixes the balls thoroughly until one comes out. Call that ball number 1. The ball is opened and you are told the value on the paper (what we will call the ‘paper value’ for short). You have the option to ‘capture’ that paper value or not. If you capture it, you put it in your capture pile and you have used up one capture. If you don’t, it goes in the discard pile never to come out, though you may find it useful to remember the discarded paper values. Repeat this procedure for all 100 balls. You are allowed three ‘captures’ altogether. Your goal is to capture the highest paper value written by your adversary. If you do, you win $100,000. If you don’t, you lose $100,000. Should you engage in this bet? If so, what is your probability of winning?

This puzzle is a variant on the sultan’s daughters problem. A young suitor may choose any of the 100 daughters of the sultan. They are presented to him in some random order. He has little basis for judgment, so judges only by outward beauty and grace. If he rejects one, he never sees her again. Once he selects one, he must marry her and no other.

Warm-Up

Can you design a strategy that gives the suitor at least a 1/4 chance of marrying the most beautiful daughter, assuming the daughters are presented to him in an order that is unlikely to be related to their beauty, e.g., based on the hour and minute of the day in which they were born?

Solution to Warm-Up

Look at but reject the first half of the daughters. Then take the first daughter who is more beautiful than any of those you have seen so far. This does not guarantee that you will marry the most beautiful daughter (or any daughter at all), but it has the virtue of offering an easy rough analysis: you have a 1/2 chance that the most beautiful daughter is in the second half and a 1/2 chance that the second most beautiful daughter is in the first half. The two together arise with probability 1/4, assuming the daughters are presented to you in an order that is independent of their beauty - a situation that likely holds in the hour-minute ordering mentioned above. That case is sufficient to ensure that you marry the most beautiful daughter. In fact, other cases also lead to this outcome. For example, the third most beautiful daughter could be in the first half and the most beautiful one could precede the second most beautiful one in the second half. A deeper analysis shows that it is better, in fact, to reject the first 37 daughters and then choose the next one that is more beautiful than any you have seen.

  1. What would be a good strategy for the $100,000 Reach for the Sky! game, where you have three captures? Using that strategy, what would be your chance of winning?

Hint: 

A bit of programming might come in handy.

  1. How would your answer change if there were 1,000 lottery balls?




Puzzles for Programmers and Pros
Puzzles for Programmers and Pros
ISBN: 0470121688
EAN: 2147483647
Year: 2007
Pages: 81
Authors: Dennis Shasha

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net