Puzzles for Programmers and Pros

1.5. 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 resiliometric 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 ...