Getting Even

Dennis, a professor of computer science at New York University, is the author of The Puzzling Adventures of Dr. Ecco (Dover, 1998), Codes, Puzzles, and Conspiracy (W.H. Freeman & Co., 1992), Database Tuning: A Principled Approach (Prentice Hall, 1992), and (coauthored with Cathy Lazere) Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (Springer Verlag, 1997). He can be contacted at [email protected].

After polite but efficient introductions, Dexter Coll began his explanation. "Wall Street is about revenue streams, Dr. Ecco. Options help us generate new kinds of streams. Mathematics, in turn, helps us ensure that those option streams yield us positive net income at low risk while providing a service for our customers."

Coll, a mathematical inventor of great renown for his seminal work in options, seemed out of place in Ecco's chaotic apartment. Oak paneling would have matched his Saville Row suit much better.

"The option we want to sell now is called a 'Getting Even' option," Coll went on. "I'm not at liberty to tell you the real context, so I will give you the problem as a story with mathematical features that are isomorphic to the problem I must solve:

"You have a friend, Fred, who is in a dangerous situation. He loves to gamble and has made the mistake of gambling with some very unsavory characters called, well, the Sharps. He wants to stop, but he doesn't want to lose a lot of money. He's afraid he'll die if he stops when the Sharps owe him a lot of money. The trouble is, he doesn't remember how much money he's winning or losing, and even more surprisingly, whether he's winning or losing. He only know he's either up or down something between $100,000 and $400,000. The Sharps, as evil as they are, are very honest about accounting and will tell him whether his outstanding credit is within $5000 of zero after every bet. If he's either winning more than $5000 or losing more than $5000, all they will tell him is that he's out of bounds. We don't like the sound of that phrase, 'out of bounds.'"

He continued, "The problem is that we don't know how to get back in-bounds. The Sharps won't let him just pay up now or, in case he's winning, just forgive the debt. They insist on being correct accountants."

"What game do they play?" Ecco asked.

"They flip a fair coin for even money," said Coll.

"At what stakes," Ecco's niece Liane asked, forever interested in gambling.

"Any integer multiple of $1000," Dexter replied.

"How can I help?" Ecco asked.

"I want you to find Fred a strategy that gets him in-bounds with as few flips as possible," Dexter said. "You can assume that the coin is fair, and that Fred has enough money to make any sized bet. Also, from now on, he will pay attention to whether he wins or loses a given bet, so he will know how much he is winning or losing relative to his current situation. Finally, he can ask the Sharps whether or not he's in-bounds after each bet. They will tell him yes or no. They always tell the truth."

"So, you want the shortest expected time in a statistical sense?" Ecco asked.

"Yes, that's exactly right," Coll said.

"What do you make of it Liane?" Ecco asked.

"Can't Fred run out of money if he bets enough?" she replied with a question.

"For now, don't worry about that. We have, I mean he has, tremendous resources," Coll said with a fleeting smile.

Everyone fell silent.

Liane was flipping coins and keeping count.

"Okay, well I can solve an easier problem," Liane said. "If we know that Fred is ahead by, say, $130,000, then we have him bet that much. If he wins, then have him bet $260,000. If he wins again, then $520,000 and so on. The first time he loses, he'll be in-bounds. On the average, he'll be in-bounds after two flips, according to my experiments."

"Right," Coll said, "but in this case, you don't know where he starts or even whether he's winning or losing."

"Yes, I know," Liane said with a sigh. Straightening up, she said, "Oh, there is one more thing though: Suppose all I know is that Fred is ahead by something between $125,000 and $135,000. Fred can still use my strategy for $130,000. The first time Fred loses, he'll be in-bounds."

Ecco looked up, smiled, and nodded, but didn't say anything. Soon, though, he was working out some calculations.

"With the values you gave me and Liane's idea, Dr. Coll," he said, "I can design a strategy for Fred that will get him to within-bounds (between positive and negative $5000, inclusive, of even) after only about 55 flips on the average. About 1 in a 1000 times, it will take him more than 140 flips."

Reader: Can you achieve an expected bound that is as good or better? If so, how? Also, how long does it take you, on the average, to get in-bounds if the bounds are between positive and negative $1000, inclusive. Ecco can do it in under 260 flips on the average.

Dr. Coll listened carefully, asked a few questions, then stood up and put out his hand. "We have not yet discussed your fee, Dr. Ecco, but you will not have to worry about finances for several years," Dr. Coll said as he and Ecco shook hands. Then he turned to Liane.

"Liane, your question about whether or not Fred could go broke was a good one," Coll said. "His total capital is $10 million. In the case where in-bounds means plus or minus $5000, how likely is it that Fred will go beyond his capital at least once in a run? What if his capital were $1 billion? We need to know the answers to both of those questions."

Liane shrugged her shoulders. "I don't know. I'll go program some experiments in K, using my uncle's suggestions." She found that the numbers were remarkably high.

Reader: How likely is it that Fred will go broke with a capital of $10 million before getting in-bounds at the $5000 level? How about $1 billion? I will eventually post Liane's simulations at http://www.kx.com/.

Last Month's Solution

The following arrangement has a happiness value of 175.

petra kris olivia felicia

mike alan

isaac larry dave

nick bob jack carol

hillary emily gwenyth

The following has a happiness value of 90 after subtracting four from everyone's value.

bob petra olivia felicia

larry kris

isaac alan dave

nick mike jack carol

hillary emily gwenyth

Reader Notes

As of this writing, many readers were able to prove two facts about the Beautiful Liars problem (June 1998):

1. There have to be at least eight liars. This follows because there are the following nonoverlapping pairs:

gwenyth alan

dave mike

sam jack

ulm larry

olivia kris

tom hillary

emily isaac

petra rivera

Since either the accuser or accused must be lying in a pair, this shows that there must be at least eight.

2. If there are eight liars, they can be only:

Dave Gwenyth Hillary Isaac Jack Larry Olivia Rivera, or

Dave Gwenyth Hillary Isaac Larry Olivia Petra Sam, or

Dave Gwenyth Hillary Isaac Larry Olivia Rivera Sam.

Approaches for this ranged from hand-checking to genetic algorithms to exhaustive search on colored graphs.

Here are the solving readers' names in the order that I received the solutions (I hope I left nobody out):

Cary Bakker

David Weiblen

Brian Hetrik

Karen Horn

Wesley T. Perkins

Michael Van Vertloo

Kent Donaldson

Warren Dougherty

Ted Alper

Michael G. McCullough

Mathew Davies

Chris Frey

Christian Tanguy

Charles Taylor

Robert H. Morrison

Thorston Koch

Ryan Fischbach

Lee Chee Meng

Elijah Pau

Michael Brackx

Iulian Kakulidis

Nicholas Sakurai

DDJ