Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Parallel

Maximum Lottery


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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.