Shasha - Dr. Eccos cyberpuzzles: 36 puzzles for hackers and other mathematical detectives

Previous Books by Dennis Shasha

Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists

Codes, Puzzles, and Conspiracy

The Puzzling Adventures of Dr. Ecco

Copyright 2002 by Dennis E. Shasha

All rights reserved
First published as a Norton paperback 2004

Many of these puzzles have appeared in a preliminary form in Dr. Dobbs Journal.

For information about permission to reproduce selections from this book, write to Permissions, W. W. Norton & Company, Inc., 500 Fifth Avenue, New York, NY 10110

Book design by Chris Welch
Production manager: Julia Druskin

Library of Congress Cataloging-in-Publication Data

Shasha, Dennis Elliott.

Dr. Eccos cyberpuzzles : 35 puzzles for hackers and other mathematical detectives / Dennis E. Shasha.

p. cm.

ISBN 0-393-05120-X

1. Mathematical recreations. I. Title: Doctor Eccos cyberpuzzles. II. Title.

QA95.S4693 2002

793.74.dc21 2003021869

ISBN 0-393-32541-5 pbk.

ISBN 978-0-393-34998-6 (e-book).

W. W. Norton & Company, Inc.
500 Fifth Avenue, New York, N.Y. 10110
www.wwnorton.com

W. W. Norton & Company Ltd.
Castle House, 75/76 Wells Street, London W1T 3QT

To the young ones:Tyler, Jordan, Max, Jacob, David, and Caroline.

Contents

Easy

Intermediate

Hard

Acknowledgments

In January of 1998, Eugene Kim invited me to write a puzzle article for Dr. Dobbs Journal. On a lark, I replied that Id be interested in recording Dr. Eccos adventures as a column. Within 4 days, editor-in-chief Jon Erickson proposed an arrangement and, under the able stewardship of managing editor Deirdre Blake, we were off. The wonderful thing about the Dr. Dobbs readers is that they are high-quality programmers who love to think. This gave me the freedom to include Ecco puzzles that could benefit from computational power, while still demanding creativity and intelligence.

Many smart readers of Dr. Dobbs Journal helped improve the puzzles and the solutions. Some, but not all are acknowledged in the solutions that follow each puzzle. My thanks extend to every reader who sent me a solution. Many improved on Eccos first cut.

As always, I have drafted my family in the solution of my puzzles. My wife Karen is my primary conscript, but my children Cloe and Tyler struggled with several of these puzzles, especially those parts aimed at cybernovices. Other family members also contributed, especially my brother Robert, my cousin Claire, and Dr. Ed.

Norton has been a wonderful publisher to work with. Editor Bob Weil and his assistant Jason Baskin made helpful suggestions with humor and insight. Production manager Julia Druskin kept me to schedule and ensured the highest quality result. Copy editor Carol Rose mixed thoroughness with good sense. Debra Morton Hoyt and Georgia Liebman deserve all credit for the design. Cover artist Matt Frost captured Ecco among his collage of thoughts. Justin Roths drawings record some of the sinister locales.

Is This Book for You?

Like so many mathematicians, Dr. Ecco loves puzzles. Fortunately for Ecco, people pay him to solve them. Joined by the narrator Professor Scarlet and Eccos brilliant niece Liane, Ecco encounters a variety of puzzles posed to him by archaeologists, space station designers, generals, (reformed) criminals, and a few normal citizens. You are asked to solve them too. Some require new mathematical thinking. For most, the absolute best answers are not known, not even to Dr. Ecco. At the same time, these puzzles require no formal background beyond arithmetic and occasionally elementary algebra, though you might decide to augment your intelligence by using a computer.

But dont worry. Even if you are not yet able to bend a programming language or spreadsheet in service to a solution, each puzzle has at least one cybernovice alternative. Alternatives so marked can be solved best by paper, pencil, and pure thought. Those marked cyberexpert usually require a technique of searching through a list of possibilities in some clever way. The best solutions to those variants are often still open.