Dennis E. Shasha - Puzzling Adventures: Tales of Strategy, Logic, and Mathematical Skill

To my extended Family, loving, energetic, and confidently odd.

Youd think that if anyone knew Dr. Jacob Ecco well it would be me. Weve appeared in photographs together. Weve taken trips together. Weve even been kidnapped together. But, in spite of the years Ive known him, he continues to baffle me.

The mystery begins with small eccentricities. He wears shorts year-round, even when its bitter cold. He refuses to wear a tie, even at events in his honor. He doesnt drink alcohol or coffee, but seldom refuses a milk shake. He climbs rocks, particularly enjoying overhangs ascending from the water, but avoids high diving boards. Tycoons pay him large fees, but his lifestyle never changes and checks lie uncashed in the mess of his desk.

Most detectives rely on observation, knowledge of human nature, and varying amounts of muscle. Ecco relies only on deduction and mathematics. The evidence for success would come from the calling cards of his clientsif he bothered to keep them.

Every one of the cases in this book is accompanied by a small passage in code. Ecco received each one on a postcard around the same time he encountered each case. Ecco has only partly decoded these. The hints seem to lead somewhere beyond the book.

The puzzles themselves came to Ecco in plain text. I present them to you in exactly the form he heard them. When some parts of the cases remain unsolved, you can try to solve them yourself, perhaps inventing new mathematics on the way. This book is not for the faint of mind.

Understanding the puzzles, however, seldom requires formal training beyond junior high school mathematics. Younger kids with sufficient imagination can solve many of them. Even adults have a chance.

Reach, touch, then grasp.

New York City

Spring 2004

P.S. Many of the puzzles themselves have appeared in abridged form in the Puzzling Adventures column of Scientific American. I expand them here to the full versions that I have heard from Dr. Ecco, often including unsolved parts. Ever the minimalist, Ecco has instructed me to remove all traces of his (or my or even his niece Lianes) presence from those puzzles. He has, however, allowed the accounts previously seen in Dr. Dobbs Journal to appear in full. Our little trio has lately acquired Lianes younger brother as a fledgling member, but those adventures are still to come.

CONTENTS

XBAG NBARELGHhLGP iP QBE MPNBiTARGSP NSLTEiLA. ci fHFG GSP NSTPQ QTEP SjOELAG.YEAPFGB

XE. YNNB iLj SLIP FHRRPFGTBAF QBE L JLhgTAR GBHE.WBiP CEPCLEPO.

Skipping the preliminaries, the detective stated his problem: We have five witnesses whom we dont trust. The five have trailed a group of 10 suspected drug dealers. For each suspect, they take a vote about whether the suspect has drugs. Here is a summary of the votes:

Suspect 1: all five vote has drugs.

Suspect 2: all five vote has no drugs.

Suspect 3: three vote has no drugs and two vote has drugs.

Suspect 4: all five vote has drugs.

Suspect 5: four vote has drugs and one votes has no drugs.

Suspect 6: all five vote has no drugs.

Suspect 7: three vote has drugs and two vote has no drugs.

Suspect 8: all five vote has drugs.

Suspect 9: all five vote has no drugs.

Suspect 10: four vote has no drugs and one votes has drugs.

Can you tell us which suspects have drugs given only that the total number of lies among all witnesses is eight or nine and most of the lies claim has no drugs when the truth is has drugs? They are a corrupt bunch.

WARM-UP.

What is the smallest number of lies there could be judging only from the accusations?

SOLUTION to WARM-UP.

Every non-unanimous vote (disagreement) must correspond to a number of lies at least equal to the minority view and perhaps the majority view. As we can see there are four occasions of disagreement: three against two occurs twice and four against one occurs twice. Adding up the minority views gives us six lies.

c VXGXUkbmr bl JIX paJ bl FIJpI Ur HTIr KXJKGX aX bl ZGTW aX WJXlIm FIJp.A.3. 4XIVFXI (t110-t2xy)

MaX TnmaJk pbGG HXXm rJn bI maX HJkIbIZ.

The celebrity governor of a certain sun-rich state shares confidences with nine advisors. To his dismay, however, some of his most intimate (and, sometimes, crude) thoughts have lately been appearing in the newspapers the day after he reveals them. A common technique for discovering leakers is to tell each suspect some unique piece of information (a tidbit) and then see if it spreads. But the governor discovers that this approach will not be good enough: newspaper editors will print a story if and only if at least three advisors attest to the tidbit. He is quite sure there are no more than three leakers. He has a dilemma. If he tells a tidbit to everyone, it will certainly be reported, but he will not have learned anything. If he tells a tidbit to one or two people, it wont be reported. He can choose a different tidbit for each triplet of people, but nine confidants can form 84 triplets. Thats just too many. The governor wants to discover the leakers faster.

He arrives at the following strategy: he will tell tidbits to foursomes, a different tidbit to a different foursome each day. Once a leak occurs, he will ask questions of triplets within the guilty foursome to discover the guilty triplet. One of his goals is to provoke no more than two additional leaksone from a foursome and, at most, one from a threesome. Another goal is to discover the triplet using at most 25 tidbits.

WARM-UP.

Suppose the governor tells a tidbit to advisors 1, 2, 3, and 4 the first day without a leak, and a second tidbit to advisors 2,3, 4, and 5 the next day with the same outcome. But his secret third tidbit, told to advisors 1, 2, 4, and 5, leaks. Which triplets are suspect? Think before you read on.

SOLUTION to WARM-UP.

Only two of the four that could be formed from the third quartet (1, 2, 4, 5) are suspect: 1, 2, 5 and 1, 4, 5. If either of the other two triplets (1, 2, 4, or 2, 4, 5) comprised the leakers, it would have leaked its tidbit during the first two days. Because the governor knows there can be only three leakers, he needs to test only one of the remaining two suspect triplets.

1. Can you help the governor guarantee to find the leakers using 25 tidbits and two leaks in all, assuming he follows the above strategy?

The governor might be able to find the precise triplet using far fewer tidbits, if sometimes he were to spread tidbits to more than four people and if he were willing to tolerate more than two leaks.

2. Can you find the leaking triplet using fewer tidbits under these conditions, perhaps tolerating more leaks? (Hint: This requires fewer than 10 tidbits.)

3. What if the governor were willing to ask more than four people, but still wants only two leaks? (Hint: You should be able to get under 15.)

Eb ukq YWj Ykqjp ukqn Kkjau, ukq Zkjp dWra W XeJJekj ZkJJWno. - F. LWqJ Cappu (w45x-w532)

Pda KeJJajeqK Xacejo sepd W psk.

Suppose you have just taken up squash and plan to play several times a week. You know you are prone to injury. There are two payment plans: a yearly membership that costs $400 and entitles you to unlimited use, or a $20 pay-per-use. How many times should you pay per use to guarantee that you wont regret your expenditure of money too much?

To make this precise, consider the situation this way: you will play every day until you get injured and then you wont play anymore. A clairvoyant oracle would know when and if you would get injured. The clairvoyant oracle would either purchase use passes or yearly memberships. You want to minimize the amount you spend divided by the amount the clairvoyant oracle would spend. Call that the regret ratio.