Dr. Dobb's | Maximum Lottery | September 01, 2005

Maximum Lottery

A lottery puzzle.

September 01, 2005
URL:http://www.drdobbs.com/parallel/maximum-lottery/184406259

September, 2005: Maximum Lottery

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].

Dr. Ecco Solution

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

September, 2005: Maximum Lottery

Dr. Ecco Solution

Solution to "Election Fraud in Verity," DDJ, August 2005.

1. There can be at most three pollsters meeting these conditions. Here's why. Each pollster must miss about 13 Wendy votes (because there are 51 in total, but only 38 seen by each pollster). No two pollsters miss the same Wendy voter, because every pair of pollsters interview all 100 voters. If we number the Wendy voters W1 to W51, then we can imagine that pollster A misses W1 to W13, pollster B misses W14 to W26, and pollster C misses W27 to W39. There are not enough more Wendy voters for a fourth pollster to miss, so there can be only three pollsters.
2. Number the Fred voters F1 to F49. Pollster A could interview W14 to W51 and F1 to F42. Then pollster B could interview W1 to W13 and W27 to W51 as well as F8 to F49. Finally, pollster C could interview W1 to W16 and W40 to W51 as well as F1 to F7 and F15 to F49.
3. As the solution to the first question showed, this result would not be possible with five honest pollsters. So Fred was right: Wendy stole the election.

Tom Rokicki helped enormously with these solutions.