THE LAST RECREATIONS © 1997 Springcr-Verlag New York, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Published in the United States by Copernicus, an imprint of Springer-Verlag New York, Inc. Copernicus Springer-Verlag New York, Inc. 175 Fifth Avenue New York, NY 10010 USA Cartoon credits: p. 237-.THE FAR SIDE copyright 1991 FARWORKS INC. Dist. by UNIVERSAL PRESS SYNDICATE. Reprinted with permission. All rights reserved. p. 284—B.C. copyright Field Enterprises, Inc. All rights reserved. Library of Congress Cataloging-in^Publication Data Gardner, Martin, 1914- The last recreations: hydras, eggs, and other mathematical mystifications/Martin Gardner, p. cm. Includes index. 1. Mathematical recreations. I. Title. QA95.G255 1997 793.7'4-DC21 96-51641 0-387-94929-1 hardback 0-387-25827-2 paperback Manufactured in the United States of America. Printed on acid'free paper. Designed by Irmgard Lochner. 9 8 7 6 5 4 3 2 1 SPIN 10561414 To Persi Diaconis for his remarkable contrihutions to mathematics and conjuring, for his unswerving opposition to psychic nonsense, and for a friendship going back to our Manhattan years. Preface One of my greatest pleasures and privileges was writing a column, over a period of some 30 years, for Scientific American. It began with an article on hexaflexagons in December 1956 and concluded with a col umn on minimal Steiner trees in May 1986- Writing diis column was a marvelous learning experience. I took no courses in madi when I was an undergraduate at the University of Chicago-my major was philosophy-but I have always loved mathemat ics, and now and dien regret I did not pursue it as a career. It takes only a gjance through earlier book collections of the columns to see how they gradually became more sophisticated as I learned more about madiematics. Not the least of my delights was getting to know many truly eminent mathematicians who generously contributed material and who have since become lifelong friends. This is die fifteenth and final collection. As in previous books in the series, I have done my best to correa blunders, to expand and update each column with an addendum, to add new illustrations, and to provide fuller lists of selected references. Martin Gardner Vll Contents Preface vii 1 TTie Wonders of a Planiverse I 2 Bulgarian Solitaire and Odier Seemingjy Endless Tasks 27 3 Fun widi Eggs, Part I 45 4 Fun widi Eggs, Part II 59 5 The Topology of Knots 67 6 M'Pire Maps 85 7 Directed Graphs and Cannibals 101 8 Dinner Guests, Schoolgiris, and Handcuffed Prisoners 121 9 The Monster and Odier Sporadic Groups 139 10 Taxicab Geometry 159 11 The Power of the Pigeonhole 177 12 Strong Laws of Small Primes 191 IX The Last Recreations 13 Checker Recreations, Part I 207 14 Checker Recreations, Part II 221 15 Modulo Arithmetic and Hummer's Wicked Witch 233 16 Lavinia Seeks a Room and Other Problems 247 17 The Symmetry Creations of Scott Kim 267 18 Parabolas 285 19 Non-Eudidean Geometry 303 20 Voting Mathematics 317 21 A Toroidal Paradox and Other Problems 331 22 Minimal Steiner Trees 345 23 Trivalent Graphs, Snarks, and Boojums 361 Index 381 I I'.' M mi U» The Wonders of a Planivcrsc "Planiversal scientists are not a very common breed.** —Alexander Keewatin Dewdney A s far as anyone knows the only existing universe is the one we live in, with its three dimensions of space and one of time. It is not hard to imagine, as many science-fiction writers have, that intelligent organisms could live in a four-dimensional space, but two dimensions offer such limited degrees of freedom that it has long been assumed intelligent two-space life forms could not exist. Two notable attempts have nonetheless been made to describe such organisms. 2 The Last Recreations In 1884 Edwin Abbott Abbott, a London clergyman, published his satirical novel Flatland. Unfortunately the book leaves the reader almost entirely in the daik about Fladand's physical laws and the technology developed by its inhabitants, but the situation was gready improved in 1907 when Chailes Howard Hinton published An Episode of Flatland. Although written in a flat style and with cardboard characters, Hinton's story provided the first glimpses of the possible science and technology of the twoKlimensional worid. His eccentric book is, alas, long out of print, but you can read about it in the chapter "Fladands** in my book The Unexpected Hanging and Other Mathematical Diversions (Simon & Schuster, 1969). In "Fladands** I wrote: "It is amusing to speculate on two-dimen^ sional physics and the kinds of simple mechanical devices that would be feasible in a flat worid.** This remark caugjit die attention of Alexander I&ewatin Dewdney, a computer scientist at die University of Western Ontario. Some of his early speculations on die subject were set down in 1978 in a university report and in 1979 in ''Exploring the Planiverse,** an article in Journal of Recreational Mathematics (Vol. 12, No. 1, pages 16-20; September). Later in 1979 Dewdney also privately published "Twcniimensional Science and Technology," a 97'page tour de force. It is hard to believe, but Dewdney actually lays the groundwork for what he calls a planiverse: a possible twoKiimensional worid. Complete with its own laws of chemistry, physics, astronomy, and biology, the planiverse is closely analogous to our own universe (which he calls the steriverse) and is apparendy free of contradictions. I should add diat this remark able achievement is an amusing hobby for a mathematician whose seri ous contributions have appeared in some 30 papers in technical jour nals. Dewdney's planiverse resembles Hinton's in having an earth that he calls (as Hinton did) Astria. Astria is a disklike planet that rotates in planar space. The Astrians, walking upright on the rim of the planet,