Dennis, a professor of computer science at New York University, is the author of four puzzle books: The Puzzling Adventures of Dr. Ecco (Dover, 1998); Codes, Puzzles, and Conspiracy (Freeman 1992, reprinted by Dover in 2004 as Dr. Ecco: Mathematical Detective); and recently Dr. Ecco's Cyberpuzzles (W.W. Norton, 2002); and Puzzling Adventures (W.W. Norton, 2005). With Philippe Bonnet, he has written Database Tuning: Principles, Experiments, and Troubleshooting Techniques (2002, Morgan Kaufmann). With Cathy Lazere, he wrote Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (1995, Copernicus/Springer). He can be contacted at [email protected].
When I arrived at Ecco's house, he had just greeted two visitors. "Jimmy Casino's the name," said the man in the beige suit and white shoes, as he offered his embossed card to Ecco. "The competition is hell out there, doc. I gotta find a new betting game to attract players. My numbers guy Janos will explain it to you."
"Dr. Ecco, we have invented a betting lottery for large stakes, based on hollow lottery balls," Janos, with his shock of disheveled blond hair, spoke with a distinct Hungarian accent. "Here is how it goes.
"Your adversary is given 100 identical pieces of paper, writes a number on each one—he can choose the range of numbers and can even put in duplicates— then folds them. Then these papers are given to an independent third party whom both sides can see. That third party shuffles the papers and then inserts one piece of paper into each of 100 hollow lottery balls that can be screwed open or shut. These balls have been tested using drop tests, bounce tests, and resiliometric tests to be sure they are all as close to equal as tolerances allow.
"The third party then puts the balls into a lottery machine. The lottery machine mixes the balls until one comes out. The ball is opened and you are told the number. You have the option to 'keep' the number. If you keep it, you put it in your keep pile and you have used up one keep. If you don't, it goes in the discard pile never to come out. (You can record the numbers on a private storage device for future reference, however). Repeat this procedure for all 100 balls. You are allowed three 'keeps' altogether. Your goal is to have the highest number written in the keep pile. If you do, you win $100,000. If you don't, you lose $100,000. Should you take the bet? If so, what is your probability of winning?"
"Echoes of the sultan's daughters problem," said Ecco with a chuckle after a few minutes of silence.
"Surely you know that one, Professor," he said. "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 to go on, so he 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 him at least a 1/4 chance of marrying the most beautiful daughter?
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 in the first half. This is not the optimal solution, 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. In that case, which happens with probability 1/4 assuming the daughters are presented to you in random order, you are sure to marry the most beautiful daughter with this protocol. In fact, your odds are better (for example, if the third most beautiful daughter is in the first half and the most beautiful one precedes the second most beautiful one in the second half) than 25 percent. A deeper analysis (check out http://mathworld.wolfram.com/SultansDowryProblem.html) shows that it is better to reject only 37 daughters and then choose the most beautiful one that follows.
Erratum in the Solution to the Treasure Arrow
Alan Dragoo pointed out an arithmetic error in my solution to the weight of the arrow in "Treasure Arrow." It should be 75 kilograms, because delta is only 15 centimeters.
DDJ
