Math text code

V

HOW THEOTHER HALF

THINKS

ADVENTURES INMATHEMATICALREASONING

2£X

SHERMAN ST

Howthe Other HalfThinks

OTHER BOOKS BY SHERMAN STEIN

Algebra: A Guided Inquiry(with Calvin D. Crabill and G. Donald Chakerian)

Calculus and Analytic Geometry, 5th ed.(with Anthony Barcellos)

Algebra and Tiling: Homomorphismsin the Service of Geometry(with Sandor Szabo)

Geometry: A Guided Inquiry(with Cal Crabill and G. Donald Chakerian)

Strength in Numbers: Discovering the Joyand Power of Mathematics in Everyday Life

Mathematics: The Man-Made Universe

Archimedes: What Did He Do Besides Cry Eureka?

Howthe Other HalfThinks

Adventuresin Mathematical Reasoning

Sherman Stein

McGraw-Hill

New York Chicago San FranciscoLisbon London Madrid Mexico City MilanNew Delhi San Juan Seoul SingaporeSydney Toronto

McGraw-Hill

A Division ofTheMcGraw-HillCompanies

Copyright © 2001 by The McGraw-Hill Companies. All rights reserved. Manufactured in the United States ofAmerica. Except as permitted under the United States Copyright Act of 1976, no part of this publication may be repro-duced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior writ-ten permission of the publisher.

0-07-138264-X

The material in this eBook also appears in the print version of this title: 0-07-137339-X.

All trademarks are trademarks of their respective owners. Rather than put a trademark symbol after every occur-rence of a trademarked name, we use names in an editorial fashion only, and to the benefit of the trademark owner,with no intention of infringement of the trademark. Where such designations appear in this book, they have beenprinted with initial caps.

McGraw-Hill eBooks are available at special quantity discounts to use as premiums and sales promotions, or foruse in corporate training programs. For more information, please contact George Hoare, Special Sales, atgeorge_hoare@mcgraw-hill.com or (212) 904-4069.

TERMS OF USE

This is a copyrighted work and The McGraw-Hill Companies, Inc. ("McGraw-Hill") and its licensors reserve allrights in and to the work. Use of this work is subject to these terms. Except as permitted under the Copyright Actof 1976 and the right to store and retrieve one copy of the work, you may not decompile, disassemble, reverse engi-neer, reproduce, modify, create derivative works based upon, transmit, distribute, disseminate, sell, publish or sub-license the work or any part of it without McGraw-Hill's prior consent. You may use the work for your own non-commercial and personal use; any other use of the work is strictly prohibited. Your right to use the work may beterminated if you fail to comply with these terms.

THE WORK IS PROVIDED "AS IS". McGRAW-HILL AND ITS LICENSORS MAKE NO GUARANTEES ORWARRANTIES AS TO THE ACCURACY, ADEQUACY OR COMPLETENESS OF OR RESULTS TO BEOBTAINED FROM USING THE WORK, INCLUDING ANY INFORMATION THAT CAN BE ACCESSEDTHROUGH THE WORK VIA HYPERLINK OR OTHERWISE, AND EXPRESSLY DISCLAIM ANY WAR-RANTY, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO IMPLIED WARRANTIES OF MER-CHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. McGraw-Hill and its licensors do not warrantor guarantee that the functions contained in the work will meet your requirements or that its operation will be unin-terrupted or error free. Neither McGraw-Hill nor its licensors shall be liable to you or anyone else for any inaccu-racy, error or omission, regardless of cause, in the work or for any damages resulting therefrom. McGraw-Hill hasno responsibility for the content of any information accessed through the work. Under no circumstances shallMcGraw-Hill and/or its licensors be liable for any indirect, incidental, special, punitive, consequential or similardamages that result from the use of or inability to use the work, even if any of them has been advised of the possi-bility of such damages. This limitation of liability shall apply to any claim or cause whatsoever whether such claimor cause arises in contract, tort or otherwise.

DOI: 10.1036/007138264X

Contents

Preface viiAcknowledgments xi

1 The Needle and the Noodle 1

2 Win by Two 19

3 The Complete Triangle 43

4 Slumps and Streaks 61

5 Thrifty Strings 73

6 Counting Ballots 97

7 Infinity 121

8 Twins 135

EPILOGUE A Backward Glance 151APPENDIXES 155

A Triangles 157 B Twins: A Supplement 161FOR FURTHER READING 167

Index 173

This page intentionally left blank.

Preface

Occasionally, in some difficult musical compositionsthere are beautiful, but easy parts—parts so simple abeginner could play them. So it is with mathematics as well.

There are some discoveries in advanced mathematics thatdo not depend on specialized knowledge, not even on alge-bra, geometry, or trigonometry. Instead they may involve, atmost, a little arithmetic, such as "the sum of two odd num-bers is even," and common sense. Each of the eight chaptersin this book illustrates this phenomenon. A layperson canunderstand every step in the reasoning.

One of my purposes in writing this book is to give read-ers who haven't had the opportunity to see and enjoy realmathematics the chance to appreciate the mathematical wayof thinking. I want to reveal not only some of the fascinatingdiscoveries, but, more important, the reasoning behind them.

In that respect, this book differs from most books onmathematics written for the general public. Some present thelives of colorful mathematicians. Others describe important

vii

Preface

applications of mathematics. Yet others go into mathematicalreasoning, but assume that the reader is adept in using algebra.

The thinking in each chapter uses at most only elemen-tary arithmetic, and sometimes not even that. Thus all read-ers will have the chance to participate in a mathematicalexperience, to appreciate the beauty of mathematics, and tobecome familiar with its logical, yet intuitive, style of think-ing. This is a book of mathematics, not a book about it.

A word about the chapters that involve random events,such as a tossed penny coming up heads or tails: We will usephrases such as "the odds of getting a heads is 1/2" or "in thelong run we expect about 50 percent of the tosses to beheads." The precise meaning of such phrases has been thesubject of extensive research by statisticians. We will inter-pret the phrases intuitively, much as William Feller did in AnIntroduction to Probability and Its Applications. As he put it,"[EJveryone has acquired a feeling for the meaning of state-ments such as 'the chances are three in five.' Vague as it is, theintuition serves as a background and guide."

Each chapter begins with a simple question about stringsmade up of two letters, usually a and b. The opening ques-tion may lead to others, which are answered in the course ofthe chapter. Strings of letters may arise in many ways, forinstance, from the wins and losses of a baseball team, theheads and tails of a tossed penny, or the pulses and no-pulsesof an electronic stream of data. Some originate in chanceevents, some in carefully planned arrangements.

Typical of this approach is Chapter 5, which raises thequestion, "How long a string of a's and b's can you makewithout repeating any triplet?" This question quickly leadsto more general ones, which we then settle with the aid ofmaps of towns and one-way roads. The answer turns out tobe of use in measuring by radar the distance to a planet, in

viii

Preface

transmitting confidential information and checking the reli-ability of a computer. Thus, while my primary goal is to illus-trate the mathematical way of thinking, if a particular resulthas applications, so much the better.

I hope this book will help bridge that notorious gap thatseparates the two cultures: the humanities and the sciences,or should I say the right brain (intuitive, holistic) and the leftbrain (analytical, numerical). As the chapters will illustrate,mathematics is not restricted to the analytical and numerical;intuition plays a significant role. The alleged gap can be nar-rowed or completely overcome by anyone, in part becauseeach of us is far from using the full capacity of either side ofthe brain. To illustrate our human potential, I cite a structuralengineer who is an artist, an electrical engineer who is anopera singer, an opera singer who published mathematicalresearch, and a mathematician who publishes short stories.

Other scientists have written books to explain their fieldsto outsiders, but have necessarily had to omit the mathemat-ics, although it provides the foundation of their theories. Thereader must remain a tantalized spectator rather than aninvolved participant, since the appropriate language fordescribing the details in much of science is mathematics,whether the subject is the expanding universe, subatomicparticles, or chromosomes. Though the broad outline of ascientific theory can be sketched intuitively, when a part ofthe physical universe is finally understood, its descriptionoften looks like a page in a mathematics text.

Still, the nonmathematical reader can go far in under-standing mathematical reasoning. This book presents thedetails that illustrate the mathematical style of thinking,which involves sustained, step-by-step analysis, experiments,and insights. You will turn these pages much more slowlythan when reading a novel or a newspaper. It may help to

ix

Preface

have pencil and paper ready to check claims and carry outexperiments.

As I wrote, I kept in mind two types of readers: thosewho enjoyed mathematics until they were turned off by anunpleasant episode, usually around fifth grade; and mathe-matics aficionados, who will find much that is new through-out the book.

This book also serves readers who simply want tosharpen their analytical skills. Many careers, such as law andmedicine, require extended, precise analysis. Each chapteroffers practice in following a sustained and closely arguedline of thought. That mathematics can help develop this skillis shown by these two testimonials:

A physician wrote, "The discipline of analytical thoughtprocesses [in mathematics] prepared me extremely well formedical school. In medicine one is faced with a problemwhich must be thoroughly analyzed before a solution can befound. The process is similar to doing mathematics."

A lawyer made the same point, "Although I had no back-ground in law—not even one political science course—I didwell at one of the best law schools. I attribute much of mysuccess there to having learned, through the study of mathe-matics, and, in particular, theorems, how to analyze compli-cated principles. Lawyers who have studied mathematics canmaster the legal principles in a way that most others cannot."

I hope you will share my delight in watching as simple,even naive, questions lead to remarkable solutions andpurely theoretical discoveries find unanticipated applica-tions.

—Sherman Stein

X

Acknowledgments

The broader its intended audience, the harder it is to writethe book. For this reason, I made sure that the various draftsof the manuscript were read by several people who well rep-resented the readers I had in mind. Max Massie, a bookman,Larry Snyder, a musician and musicologist, and Joshua Stein,a lawyer, made countless improvements in the exposition.My wife, the poet Hannah Stein, not only repaired sentencesand rearranged paragraphs, but kept me human during themonth upon month I spent at my desk. The mathematiciansGeorge Raney and G. Donald Chakerian substantially clari-fied the exposition.

My editor at McGraw-Hill, Amy Murphy, meticulouslywent through the final version, making suggestions thatimproved every chapter. This is the first time in my experi-ence as an author that an editor has been so involved in thedetails of making a book as good as it can be.

Both the readers and I are deeply indebted to them.

xi

This page intentionally left blank.

CHAPTER ONE

The Needle andthe Noodle

Georges Buffon (1707-1788) made his reputation withthe publication of his multivolume Natural History,General and Particular, which brought order to much ofwhat was known about the animal and mineral worlds. In anappendix totally unrelated to natural history, he includes amainly mathematical work, titled Essay on Moral Arithmetic.One of the problems he discusses there concerns a needledropped at random on a floor furnished with regularlyspaced parallel lines.

"I suppose that, in a room where the floor is divided byparallel cracks, one throws a stick into the air. One gamblerwagers that the stick will not cross any cracks. The other, onthe contrary, wagers that it will cross some of them. What arethe odds of winning for each of the gamblers? (One couldplay this game with a needle or a pin without a head.)"This is known as the Buffon Needle problem.

I

How the Other Half Thinks

The Needle

For convenience we will assume that all the lines (cracks) arethe same distance apart, namely, the width of the slats, and thatthe length of the needle is the same as the distance between thecracks. We also assume that these lengths are 1 inch.

Buffon and the two gamblers want to know the likeli-hood that the needle will miss all the lines and also thelikelihood that it will cross a line. Because the needle is notlonger than the distance between the lines, it cannot crosstwo lines. (The case in which the needle lands perpendicularto the lines with its ends just touching the lines occurs sorarely that it will not affect our reasoning.) The typical possi-bilities are shown here.

We assume that the room is of infinite size. That is, thelines are infinitely long, and there is an infinite number ofthem. That way, our thinking will not be complicated by aborder.

It may seem that the answer to Buffon's question willrequire a good deal of geometry. However, our reasoningwill require none at all, in keeping with my promise in theintroduction.

2

The Needle and the NoodleExperiments

It is tempting to guess that the needle will miss the lines asoften as it crosses a line. But before we speculate, we shouldmake an experiment. The parallel lines can be supplied by awood floor or by a floor paved with square tiles. Lackingsuch a floor, one could draw parallel lines on several pieces ofnewsprint taped together. A piece of wire as long as the dis-tance between the lines can serve as the needle.

When carrying out the experiment, give the needle agood spin so that it doesn't always fall at the same angle.Also, to help achieve randomness, change the direction inwhich you stand.

I tossed the needle 100 times. There were 66 cases inwhich the needle crossed a line and 34 in which it did not.That is pretty far from the guess that the 2 cases would besplit evenly. The results of the first 50 of these throws arerecorded in the following string of h's and m's, where an hstands for hitting a line and an m for a miss:

hhhmhmmhmhhmhmhhmhhhmhmhhmmhmhmhmhhhmmhhmhhhmhmhhh

There are 31 hits and 19 misses. Of the next 50, 35 are hitsand 15 are misses.

But what are the exact odds? I mean, as we toss the nee-dle many times and the string of h's and m's gets longer, whatwill happen to the percent that are h's}

I find it strange that that percent does tend to settle downand stay closer and closer to some number. After all, the nee-dle has no memory. Each toss is totally independent of all theearlier tosses, yet the percent of hits tends to stabilize asthough the needle does remember and wants to hit a line in

3

How the Other Half Thinks

the long run a certain fraction of the time. We will find thatfraction.

Rewording the Problem

On any toss, the needle hits either no lines or one line. To putit another way, there are either no crossings or one crossing.Thinking in terms of crossings, we may ask, "What is theaverage number of crossings when a needle is tossed billionsof times?"

In my experiment there were 66 crossings in 100 trials.That is an average of 66/100, or 0.66 crossings per trial.Therefore, we expect our theoretical average, the one forbillions of throws, to be somewhere near 0.66. Whatever theanswer is for crossings, it will also tell us the likelihood ofthe needle's hitting a line.

The advantage of this version in terms of crossings, intro-duced by Emile Barbier (1839-1889) in 1870, is that it easilygeneralizes to other geometric shapes. We now ask, "If wehave a thin wire of any shape and length, what will be theaverage number of crossings of the lines when we throw itbillions of times?" It turns out, as we will soon see, that thismore general question can easily be settled by elementarymeans. That the more general case turns out to be easier thanthe specific case is not unusual in mathematics and the sci-ences. The key to finding the answer may lie in asking theright question. The correct question may offer a clue to itsown answer.

The Noodle

Consider any rigid wire made up of straight pieces weldedtogether. The wire must be "flat" in the sense that when it

4

The Needle and the Noodle

falls on the floor, all of it touches the floor. Here are some ofthe possible shapes.

The wire could be straight and of any length, a letter of thealphabet, a spiral, or whatever comes to mind.

We will consider only wires in the shape of polygons. Apolygon is a figure made of straight segments. In classicalgeometry a polygon forms a closed circuit, but we will usethe term more generally.

We now ask a far more general question than the oneabout the needle: Handed a flat piece of wire, made ofstraight pieces and of a certain length and shape, we ask,"How can we predict the average number of crossings whenwe throw the wire many, many times?" In a 1969 paper onthis question, J. F. Ramaley called this the "Buffon Noodle"problem.

For instance, the Z-shapedwire shown to the right can have0,1,2, or 3 crossings. We disregardthe rare case when a segment hap-pens to lie on one of the lines. Theaverage number of crossings mustlie somewhere between 0 and 3.

This time it is hard even toguess the answer, for the average depends on the particular

5

How the Other Half Thinks

wire. The only case in which we have any data at this point isthat of the needle, which is as long as the slats are wide.

We restrict our study to polygons—figures made up ofstraight-line segments—to simplify the mathematics. How-ever, any reasonably smooth curve can be approximated bypolygons made up of very short pieces, even pieces all of thesame length. Because of this, our theory applies even tocurves. In fact, it even applies to polygons and curves madeof flexible string instead of rigid wires. For this reason wemay speak of Buffon's problem for a wet noodle.

Though we seek a theoretical answer, experiments willserve as a check and may even suggest a solution. Wewill start with the simplest cases, a common tactic of mathe-maticians, almost the opposite of another tactic, illustrated inthis chapter, which is to generalize.

Experiments

To describe a particular wire, we will use its length and shape.We will assume that the lines are an inch apart. That way, wecan easily measure lengths with an ordinary measuring tapeused in sewing.

Let us begin with a needle twice as long as the needlewe started with. It is 2 inches long and thus can have 0, 1,or 2 crossings. Recall that as we throw it, we give it agood horizontal spin in order to help make the throwrandom.

Imagine that a bug rides the needle—a bug that will helpus in later chapters as well. When the needle lands, the bugcrawls from one end to the other and reports how often hecrosses a line.

I threw this needle 20 times, with the number of cross-ings shown here in detail in the order they occurred: 1 2 2 0 202122221011212 2. There were three 0s, six Is, and

6

The Needle and the Noodle

eleven 2s. So the average number of crossings per throw, thatis, the total number of crossings divided by 20, is

3x0 + 6x1+11 x220

That is, 28/20 = 1.4. On average, then, the straight wire that is2 inches long had 1.4 crossings per throw in this experiment.

Then I bent this same wire into the shape of a V witharms of equal lengths. Here are the numbers that the bugreported for 20 throws: 21212121121211211011.This time there were one 0, twelve Is, and seven 2s, for atotal of 26 crossings. That is an average of 1.3 crossingsper throw.

Next I bent the same wire into a square. The numberof crossings for the 20 throws was 0222022222202002200 2. (This time there could not be any Is be-cause when a square crosses a line, it crosses it twice. Wedisregard the rare case when the square just touches a line.)Since there were 26 crossings, the average per throw is26/20 = 1.3.

Recall the 100 throws of the 1-inch-long needle, duringwhich there were 66 crossings. In this case we see that theaverage was 66/100, which is 0.66 crossings per throw.

I went on to bend the same 1-inch wire into a Z. Nowthere could be anywhere from 0 to 3 crossings in a throw.Here are the bug's reports on 20 throws: 30010100011001001121. This gives a total of 13 crossings in20 throws for an average of 13/20 = 0.65 crossingsper throw.

All these averages are only suggestive. They are based ononly a few throws, not on thousands. However, they mayguide us as we frame a theory that does not depend on anyexperiments.

7

How the Other Half ThinksInterpreting the Data

All our experiments are summarized in this table:

Average Number of

Shape

Length''"

Crossings per Throw

Straight

1

0.66

Straight

2

1.40

V

2

1.30

Z

1

0.65

Square

2

1.30

"'Length of wire.

You could easily add to the list, using longer wires and othershapes. The only two factors that can influence the averageare shape and length. Looking at the data, skimpy thoughthey may be, we are tempted to say that shape has little oreven no influence on the average number of crossings. Forinstance, changing the 2-inch wire from straight to a V andthen to a square seems not to affect the average significantly.Changing the length, however, exerts a large influence. Let ustake a look at the role of shape first.

The Influence of Shape

Let us use common sense to compare the two cases of a wireof length 2, straight and bent into a V. The experimental aver-ages for these shapes were close to each other, 1.40 and 1.30.

Once again we summon bugs to assist us.

First consider the straight needle. Instead of one bugreporting crossings, let us have two bugs. Each bug wandersover his half of the needle, as shown below.

One bug reports cross-

I the needle, and the other

8

The Needle and the Noodle

bug reports crossings of the right section. Each will report a0 or 1 because each section of the needle is as long as thewidth of one slat. To learn the total number of crossings ofthe whole needle, we listen to the two bugs, and we add thetwo numbers they utter.

Neither bug knows about the other bug. Indeed, eachknows only his own section and is not aware that there isanother section. Each bug thinks that his section is beingspun and thrown at random.

The average number of crossings for the whole needle isthe sum of the averages the two bugs report. Keep this inmind as we now bend the needle into a V.

The wire, which had been straight, is now a V. The twobugs have no idea that they now ride on a bent wire. Afterall, each of them is aware only of his own section. More-over, each is responsible only for reporting crossings of hissection.

As the V-shaped wire is thrown at random, each of itstwo sections is also thrown at random. As far as the bugs areconcerned, their sections are being thrown just as they werewhen the wire was straight. Therefore, each bug reports thenumber of crossings now as it did before, when it was ridinghalf the straight needle. Therefore, the average number ofcrossings for each bug observed is the same as before. It fol-lows that the (theoretical) average number of crossings forthe V is the same as for the straight needle of the same length.Thus we conclude that bending the straight wire into a V oftwo equal arms has no effect on the average number of cross-ings if the wire is thrown not just 20 times but millionsof times.

However, we don't know at this point what that averageis. The experiments suggest that it is somewhere in the vicin-ity of 1.30 and 1.40.

9

How the Other Half Thinks

Our analysis applies to any wire that is bent into theshape of a polygon. As a reminder, here are a few polygons,some of which we have already looked at.

To analyze the Z-shaped polygon, we call upon the service ofthree bugs. Place one on each of the three sides. (The sidesdon't have to be the same length.) Each bug has no idea thathe is riding on a Z-shaped wire. He thinks he is crawlingabout on a much shorter straight wire and must report thatsection's crossings of the lines in the floor.

Now straighten the Z without dislodging the bugs, anddon't even tell the bugs what you are doing. The three bugsnow report on the three sections of a straight wire. Theyreport the same number of crossings, on average, as they didwhen they were crawling on the Z. The figure below con-trasts the "before" and "after."

When the whole Z-shaped wire is thrown at random, so iseach of its three sections. The average number of crossingsfor the Z is therefore the same as for the straight wire of thesame length. This argument applies to any polygon. Justplant a bug on each of its segments and reason as we did forthree bugs. We can therefore say that shape has no influence

10

The Needle and the Noodle

on the average number of crossings of the wire and the linesin the floor.

The Influence of Length

Now that we have ruled out shape as an influence on theaverage, we are left only with length as a factor. Let us seehow the average behaves as we change the length of the wire.We might as well assume that the wire is straight since thatcase is easiest to draw.

The straight wire of length 2 inches has an average of 1.40crossings, which happens to be about twice the average forthe wire of length 1. That comparison is based just on exper-iments. What do the bugs tell us about the comparison if bil-lions of throws are made?

Imagine two bugs on the 2-inch-long wire. Each isresponsible for half the wire, as shown here.

1 in *J-< 1 in

Once again each bug is unaware of the other bug and theother section. Each reports approximately the same totalnumber of crossings when the wire is thrown billions oftimes. Therefore the total number of crossings for the wholewire of length 2 will tend to be twice the total number for thewire of length 1. Doubling the length will double the averagenumber of crossings.

What if one wire is, say, 2/3 as long as another wire? Inthis case, divide the longer wire into three sections of equallengths and place a bug on each section, like this.

How the Other Half Thinks

The part of the wire, AC, is 2/3 as long as the whole wire,AB. Since there are two bugs on AC and three bugs on AB,the number of crossings of the part AC will tend to be 2/3 thenumber of crossings of the whole wire. This tells us thatthe average number of crossings for the shorter wire is 2/3the average for the whole wire.

This type of reasoning shows that the average numberof crossings for a long wire is greater than that for a shortwire. Moreover, the average is proportional to the length.Another way to say this is "If for a wire, you divide theaverage number of crossings by the length of the wire, youwill get a number, and this number is the same for allwires."

Let us check that claim for the five wires whose data werecorded in a table:

Average Divided by

Shape

Length

Average

Length

Straight

1

0.66

0.66/1 = 0.66

Straight

2

1.40

1.40/2 = 0.70

V

2

1.30

1.30/2 = 0.65

Z

1

0.65

0.65/1 = 0.65

Square

2

1.30

1.30/2 = 0.65

The Missing Number

Thanks to the bugs, we know that for any wire, if we dividethe average number of crossings by the length of the wire, weshould get the same number as we would for any other wire.This is in fact the case for any curve or polygon. The preced-ing table suggests that the average divided by the length issomewhere near the range 0.65 to 0.70. But what is this miss-

12

The Needle and the Noodle

ing number exactly, which is the key to our whole study ofcrossings? What is this "universal constant" that is notaffected by shape or length?

Since the only "famous" number that is near the experi-mental results is 2/3, we may be tempted to guess that themissing constant is 2/3. As we will see in a moment, thatguess is wrong.

Cutting more wires, bending them into various shapes,and then tossing them on the floor, even were we to throwthem trillions of times, will not help us find this constant.That would give us only better estimates. Instead, to find thatmissing constant—the key to the whole chapter, the numberthat will answer Buffon's original question about a needle—we will have to figure it out by common sense, by purethought.

The Constant Found

If we could find the constant for just one wire, we wouldthen know it for all possible wires. Which wire will best serveour purposes? Surely not the needle, for we have no way tofigure out its average number of crossings any better than wealready have with our experiments.

Luckily, there is a certain wire whose average numberof crossings we can work out without throwing it evenonce. That wire is a circle of diameter 1, the same as thewidth of the slats, the distance between the parallel lines onthe floor.

First, we know the circumference (length) of a circle. It is7t times the diameter. In our case the diameter is 1, so thecircumference is 71, whose decimal begins 3.141592. (Toremember the digits, say "How I wish I could recollect pi."The length of each word gives a digit.)

13

How the Other Half Thinks

The average number of cross-ings for this circular wire is easyto find, as shown here.

No matter where the wirelands on the floor, there willalways be two crossings. (Wecount "just touching" as a cross-ing. After all, the conscientiousbug would report it.) So theaverage must be 2. For this par-ticular shape, then, we have an average of 2 and a length of Jt.When we divide the average by the length, we do not get 2/3 asour missing universal constant, but 2/n, or 2/(3.141592),which is just under 0.64. That is just a little less than our exper-imental results, which were in the 0.65 to 0.70 range.

Back to Buffon's Needle

Buffon's original question was not about the average numberof crossings. Rather, it asked, "What fraction of the timesthat you toss a needle, whose length is the distance betweenlines, does it hit a line?" However, we noticed that that is thesame as the average number of crossings for this particularwire. Since the length of the needle is 1, we have

Average _ 2^

This equation tells us that the average is 2/n, or about 0.64.That means that the needle will land on a line about 64 per-cent of the time.

It's rather strange that we used a circle to answer a ques-tion about a straight object, the needle. But we could also goin the reverse direction, using the straight needle to find infor-

14

The Needle and the Noodle

mation about the circle. We could throw the needle thousandsof times and compute the fraction of times it crossed a line.That would give an estimate of the fraction 2/71, from whichwe would be able to obtain an estimate of 71 itself.

Buffon answered his question by the use of calculus, whichwas invented near the end of the seventeenth century by New-ton and Leibnitz. The more elementary solution presented inthis chapter exploits the link between length and crossings.

This problem introduced the field now known as geo-metric probability, which combines geometry and probabil-ity theory. Moreover, before this problem was posed,probability theory was concerned only with situations with adiscrete set of possible outcomes (for instance, the likelihoodof getting various totals when two dice are thrown). In con-trast, a needle can occupy a continuous array of positions rel-ative to the lines in the floor.

An Application

I would like to include one discovery that is easily estab-lished with the aid of our result about the average number ofcrossings.

Consider a rigid wire in the shape of a convex loop, thatis, a loop without dents. (The formal definition is that when-ever two points lie in the region bounded by the wire, so doesthe whole line segment that joins them.) When such a wirecrosses a line, it usuallycrosses it exactly twice.

The loop casts ashadow in every possibledirection, as illustratedhere, which displays justthree of its shadows.

Shadow

15

How the Other Half Thinks

It has been shown that the length of the curve is equalto n times the average shadow length. This is quite a general-ization of the relation between the circumference and diame-ter of a circle, a case in which all the shadows have the samelength, namely, the length of the diameter.

However, by counting crossings, we will see why theaverage shadow length is related to the length of the wire.

For convenience we start again with parallel lines 1 inchapart and a wire so small that wherever it falls it never crossestwo lines. The wire can fall at any angle with respect to thelines. Let us focus our attention on the case of just one typi-cal angle, as illustrated below. Throughout our discussion,we keep this angle fixed.

The wire crosses a line whenever its shadow perpendicularto the lines crosses a line, as shown below.

16

The Needle and the Noodle

This relation is the key to our reasoning that follows.

When the shadow crosses a line, the wire has two cross-ings with that line. The longer the shadow, the more likelyit is that the wire crosses a line. To find out how likely, con-sider the next figure, in which the width of the shaded bandis the same as the length of the shadow.

The shadow meets a line when its left end lies in a shadedband, as shown here.

The likelihood of this happening is simply the width of theband since the lines are all 1 inch apart.

Consequently, the likelihood that the wire, falling at thegiven angle, hits a line is just the length of its shadow perpen-dicular to the lines. When it does hit a line, there are two

17

How the Other Half Thinks

crossings. Thus the average number of crossings, when thewire falls in any given angle, is

2 times the length of the shadow perpendicular to the lines

That is the key to our analysis.

Since the wire can fall at any angle, the average number ofcrossings is

2 times the average shadow length

Now, recall that

Average number of crossings _ 2^

Therefore,

2 times average shadow length 2^

Dividing both numerators by 2 gives us

Average shadow length _ 1_

This last equation tells us that the wire is K times as long as itsaverage shadow. That is what we wanted to show.

The argument we used for short wires can easily betweaked to apply to any convex wire. Just place the lines farenough apart so that the wire cannot cross two lines. Thenuse the distance between those lines as the unit of measuringlengths. Incidentally, the relation between the length of aconvex wire and its average shadow was established by theFrench mathematician Augustin Cauchy (1789-1857) in1841, using calculus.

In 1977 a conference of some 15 mathematicians and 15biologists was held in Paris to mark the 200th anniversary of

18

The Needle and the Noodle

Buffon's problem. The title of the meeting was "BuffonBicentenary Symposium on Geometrical Probability, ImageAnalysis, Mathematical Stereology, and Their Relevance tothe Determination of Biological Structures." As an indica-tion of the variety of the research, one paper described workrelated to "forestry sample surveys." The report of the pro-ceedings opened with a reproduction of Buffon's own dia-gram of his needle problem.

Clearly Buffon's problem has repercussions to this day.

19

This page intentionally left blank.

CHAPTER TWO

Win by Two

1 n the game of volleyball the winning team must have a cer-Itain number of points, for instance, 25 in internationalmen's contests. They must also have a margin of at least 2over the losing team. This means that if the score is 25 to 24,the game is not over. It also tells us that the score just beforemust have been tied at 24 to 24.

Let's take a look at a game in which the score is tied at 24to 24. Evidently the two teams are evenly matched. Presum-ably they have equal odds of winning any particular point. Inthat, they resemble, perhaps, a tossed penny that can comeup either heads or tails. Later we will take a second look atthis assumption.

The game goes on until one team leads by 2 points. Intheory the game could continue for hours, perhaps forever. Ifthe teams split the next 2 points, the score would then be 25to 25. Then they could split the following 2 points, the scorereaching 26 to 26. Perhaps one team would then win the next

2 points and emerge victorious, with the score 28 to 26.

21

How the Other Half Thinks

Close games like these can end with scores of 26 to 24, 27to 25, 28 to 26, and so on. This scoring situation raises twoquestions: In such games, how many points do the teamshave to play on the average before a game ends ? What is themost common final score?

We will approach these questions three ways. Firstwe will examine the records of past volleyball matches,focusing our attention only on ones that were tied at 24to 24.

Second, we will flip a penny to simulate the points wonor lost by the two teams. Heads will mean one team wins,and tails that the other team wins.

Third, we will use just common sense, answering thequestions without appealing to volleyball records or aflipped penny. That doesn't mean that our first two effortswill be wasted. They serve as checks on our common-senseapproach, as we will see.

If the two teams are the Atlanta Aphids and the Balti-more Beetles, we will let an a stand for a point for Atlantaand a b for a point by Baltimore. Thus we can record thegame as a string of as and b's.

In the rest of the chapter we will be interested only inthe points played after the 24-to-24 score. For instance, thestring aa tells us that Atlanta won the next 2 points andthe game was over at 26 to 24. The string abbaaa tells us thatthe two teams split the next 2 points (and were tied at 25 to25) and the next 2 (and were tied at 26 to 26), and thenAtlanta won 2 points in a row, emerging victorious with thefinal score of 28 to 26.

The shortest possible string at the end of such a game haslength 2, either aa or bb. The next shortest string has length4, such as babb. The length of a string of interest to us has

22

Win by Two

any of the lengths 2, 4, 6, . . . , in short, any even number.(For instance, say that the game ends with the Baltimore Bee-tles winning. Then there will be two more b's than a's. There-fore, the number of a's and the number of b's will both beeven or both be odd. In either case their sum is even. Thesame holds if the Atlanta Aphids win.)

The two questions now read: What is the average lengthof the strings that come from close games? What is their mostcommon length?

Volleyball Records

First let's take a look at what happened in some actual vol-leyball games. During the 1999 and 2000 seasons, the U.S.national men's volleyball team played 64 games that weretied at 24 to 24. Here is how the final scores turned out inthese cases:

Score

Number of Games

26-24

24

27-25

12

28-26

4

29-27

4

30-28

7

31-29

4

32-30

3

33-31

1

34-32

0

35-33

0

36-34

2

37-35

0

38-36

3

23

How the Other Half Thinks

Remember that we are interested only in points made afterthe score was tied at 24 to 24. (The earlier part of the gamedoes not concern us.) Thus for us a score of 26 to 24 meansthat the score after the 24-to-24 tie was 2 to 0. A 27-to-25game means a score of 3 to 1 after the tie. With thisperspective, we replace the preceding table with the follow-ing one:

Score'""

Number of Games

2-0

24

3-1

12

4-2

4

5-3

4

6-4

7

7-5

4

8-6

3

9-7

1

10-8

0

11-9

0

12-10

2

13-11

0

14-12

3

' After tie.

To simplify matters further, we record just the totalnumber of points made after the game had reached 24 to 24.For instance, the total in a 2-to-0 game is 2; in a 3-to-lgame, it is 4; and so on. If we know the total number ofpoints, we can figure out the number of points each teamscored. For instance, if the total is 8, then the winner had 5points and the loser 3. The total has to be even since it is

24

Win by Two

either the sum of two even numbers or else the sum of twoodd numbers:

Total Points

Number of Games

z

A**

A

1 0

D

*r

QO

/(*r

12

4

14

3

16

1

18

0

20

0

22

2

24

0

26

3

The most frequent number of points played after thegame had reached 24 to 24 is 2. That is as quick as can be:One team wins both points, the other none. Next most fre-quent is the case in which 4 points are played. The teams splitthe first 2 points, then one team goes on to win the next 2points. The data suggest that shorter games are more fre-quent than longer ones.

To find the average length of a game, we add up the totalpoints played and divide that sum by the number of games,which is 64. This sum would have twenty-four 2s, twelve 4s,and so on. Thus the average number of points scored afterthe 24-to-24 stage is the following fraction:

(24x2) + (12x4) + (4x6) + (4x8) + (7x10)+ (4x12) + (3x14) + (1x16) + (0x18)+ (0x20) + (2x22) + (0x24) + (3x26)

25

How the Other Half Thinks

This equals

48 + 48 + 24 + 32 + 70 + 48 + 42+ 16 + 0 + 0 + 44 + 0+78

or

450

This fraction equals about 7.03. For those 64 games, the aver-age number of points played after the 24-to-24 tie was there-fore about 7.

Now let us see what a penny tells us.

The Penny

Since the teams were tied at the end of 48 points at 24 to 24,it is reasonable to assume that they are equally matched.Therefore, we will assume that each team has the samechance of winning any rally. That means each team has a 50percent chance, or 1/2, of winning any particular point. Forthis reason we suspect that their play should resemble thefate of a tossed penny that is equally likely to come up headsor tails. We interpret heads as a point for Atlanta and tails asa point for Baltimore. Later we will see that the assumptionthat the two teams behave like tossed pennies is only a firstassumption, and it has to be modified.

This comparison suggests that we toss a penny to imitatetwo teams playing volleyball. We flip it until the total num-ber of heads exceeds the total number of tails by 2, or thetotal number of tails exceeds the total number of heads by 2.We then record the total number of tosses, which could be asfew as 2. However, just as with a volleyball game, we mayhave to toss the penny many times.

26

Win by Two

Here is a record of a penny experiment that needed 10tosses:

ab\ab\ba\ab\bb

An a stands for heads, a b, for tails. I put the vertical bars into make it easier to see at a glance what happened. The num-ber of heads equaled the number of tails at the end of 2, 4, 6,and 8 throws. Then 2 tails showed up, and tails obtained alead of 2. The "score" then is 6 to 4. This corresponds to avolleyball game during which 10 points were played afterthe 24-to-24 tie and the total score at the end was 30 to 28.

I performed the experiment 64 times, the same as thenumber of volleyball games. In each experiment I tossed thepenny until the number of heads differed from the number oftails by 2. The following table records the results:

Total Number

Number of Times

2

31

4

14

6

8

3

10

2

12

3

14

1

16

0

18

1

20

1

In both cases, the volleyball and the penny, the most fre-quent total is 2, the next most frequent is 4, then 6. Volleyballhas more long runs than the penny. Because of these longruns, the average for volleyball is probably larger than the

27

How the Other Half Thinks

average for pennies. The penny's average run is the followingfraction:

(31x2) + (14x4) + (8x6) + (3x8) + (2x10)+ (3x12) + (1x14) + (0x16) + (1x18) + (1x20)

This equals

62 + 56 + 48 + 24 + 20 + 36+14 + 0 + 18 + 20

which is

298

This equals about 4.66, lower than the 7.03 average for thevolleyball games. That discrepancy is so large that it hardlycould be due to chance. Later we will have an explanationfrom volleyball experts for the difference.

You are invited to perform your own experiments with acoin of your choice and compare the results with the onesdescribed.

An Approach without Experiments

To make better estimates, we could either collect more dataon volleyball tournaments or throw a penny many times,perhaps thousands of times. If we had a computer with arandom-number generator, we could run off a million caseswhile we slept. In any case, the more we experiment, themore reliable our estimates will be.

There is, however, a method for predicting the frequen-cies of the various scores without doing any experimentswhatsoever. In this approach we combine our common sense

28

Win by Two

with a little arithmetic. The experiments will not only guideus but, when we are done, serve as a check on our thinking.

To begin, look closely at the fraction that represents theaverage for the 64 penny trials:

(31x2) + (14x4) + (8x6) + (3x8) + (2x10)+ (3x12) + (1x14) + (0x16) + (1x18) + (1x20)

Dividing each term by 64, we rewrite this as the sum of sev-eral fractions:

(31x2W^x4W^-x6) h ' 3 x8i + |-2-x^|

+ ( — x12] + P- x14] + | — x16] + — x18| + f— x20)

This expression is the sum of 10 quantities. Each is a fractiontimes an even whole number.

What do the fractions mean? The first, 31/64, is thefraction of the 64 experiments that had a total of 2. The sec-ond is the fraction of times that the total was 4, and so on.If we performed billions of experiments, what wouldhappen to these fractions? In other words, using just com-mon sense, how would we expect those fractions to behave?Would they wander all over, or would they tend to getcloser and closer to some fixed fraction? If the latter hap-pens, what would we expect that fixed fraction to be?

Let us now think this through. Imagine tossing a penny.In the first two tosses any of four outcomes can occur:

aa (heads, heads) ab (heads, tails)ba (tails, heads) bb (tails, tails)

These four possibilities are all equally likely since the pennyis just as likely to come up heads as tails. Two cases—namely,

29

How the Other Half Thinks

aa and bb—result in a difference of 2 between heads and tails.So we would expect that on average two out of four trialswould end with a score of 2 to 0. On the other hand, the casesab and ba result in ties at 1 to 1.

Imagine that there were 1000 games that were tied at 24to 24. We would expect about half of them, that is, 500, to beover after just 2 more points are played. Also 500 would betied at 25 to 25. Then 2 more points are played. In halfof these cases one team takes a 2-point lead and the gameis over with a score of 27 to 25. In 250 games the score isagain tied.

We see that in 1000 close games, there would be around250 that would end with a score of 27 to 25. That is a quarterof the games. In terms of the penny, we see that about onequarter of the experiments would end with a total of 4 tosses.As a check, let us compare this conclusion with the data.

There were 14 cases out of 64 in which the total was 4.That is very close to our theoretical 1/4. As percents, 14/64 isabout 22 percent, while 1/4 is exactly 25 percent.

We expect half of the trials to end after just 2 tosses and aquarter to end with 4 tosses. So three quarters of the trialsend with a total of 2 or 4 tosses. It follows that one quarterwill go on longer.

Which ones go on longer? Those in which the first 2tosses are opposites, a head and a tail in one order or theother, and the next 2 tosses are also opposites. This occurs in1/4 of the trials. In half of these cases the next 2 tosses will beaa or bb, resulting in a lead of 2 at 6 tosses. Since half of 1/4is 1/8, we expect a total of 6 to occur in one eighth, or 12.5percent, of the trials. In our experiment the observed fractionwas 8/64, which is exactly 1/8, the predicted value.

Continuing this reasoning tells us that the fraction of tri-als that end with 8 tosses is 1/16. The theoretical fractions so

30

Win by Two

far are 1/2, 1/4, 1/8, 1/16. The pattern goes on this way, eachfraction being half the preceding one.

Here is one way to see why this is so. In a trial, group thetosses into pairs, as indicated in this diagram, which shows atypical case of a lead of 2 arising after 10 tosses:

Each dash would hold an a or a b. The vertical bars separatethe tosses into pairs.

In the first block of 2 there must be a tie, one a and one b.That happens half the time. The same must occur in the nextblock of 2. So in half the cases in which there was a tie in thefirst block, there is also a tie in the second block. So in half ofa half, or a quarter, of the trials, there is a tie at the end of 4tosses. In half of these cases there will be another tie in thenext block. So in one eighth of the times there is a tie atthe end of 6 tosses. Similarly, at the end of 8 tosses, there is atie in one sixteenth of the cases. But in the fifth block of 2either 2 heads or 2 tails appear. That occurs in half the casesin which there was a tie at the end of 8 tosses. All told, then,a total of 10 should occur on average about once in 32 trials.That's about 3 percent; we had 2 in 64 trials, which is in thesame proportion.

It follows from this line of reasoning that the averagenumber of tosses until there is a lead of 2 (if we threw thepenny billions of times) is

(1x2) + (1x4) + (lx6) + (J-xs) + (^xio) + • ••

The three dots are shorthand for "keep on adding more andmore terms formed in the same manner: Keep doubling thedenominators and increasing the multipliers by 2. Never stop."

31

How the Other Half Thinks

Playing with Endless Sums

We now have two views of the average in which we are inter-ested. First, we have data collected from volleyball games andtossed pennies. Second, we have an endless sum derived bycommon sense.

What does this seemingly endless sum mean? It makes nosense to add up an infinite number of numbers. No one cando that, not even with the aid of a computer executing bil-lions of operations per second. It does make sense, however,to add up the first thousand terms in the sum, or the first mil-lion, or the first billion terms.

We can imagine adding up more and more terms andwatching what happens to the sums. If they look as thoughthey are getting closer and closer to a fixed number, we willcall that number the sum of the infinite number of terms. Aslong as we keep in mind that we always add up only a finitenumber of terms, there should be no trouble with the mis-leading phrase "the sum of an infinite number of terms." Theterms are said to form a sequence, or series.

"With this warning in mind, let us tackle the "sum" of theseries

1x2) + (1x4^ + (1x6^ + (-1-X8

+ I —x1ol +

Let us add up the first six terms, just to get a sense of how thesums behave:

(1x2^ + (1x4^ + (1x6

; I — X 8 I + ( — X 10 1 + ( — X 12|

32

This sum is

Win by Two

2 4 6 8 10 12

— + — + — + — + — + —

or roughly

1 + 1 +0.75 + 0.50 + 0.31 +0.19

which is 3.75.

That is promising, for 3.75 is in the same ballpark as theexperimental average for the pennies, 4.66. However, we stilldon't know what will happen as we add more and moreterms. You may want to add a few more terms yourself, withor without the aid of a calculator.

Practice

Consider, for practice, a simpler sum in which the multipliersare all replaced by 1 s—namely, the sum

11111

—+—+—+ — + — + • • •

For instance, the sum of the first 4 terms, when each isexpressed with a common denominator 16, is

8 4 2 1

— + — + — + —

which equals 15/16, or 0.9375. The sum of the first 10 termsis 0.9990 to four-decimal-place accuracy. It looks as thoughthe sums are approaching 1.

A glance at the diagram to the rightof a square cut into an infinite number ofrectangles will show that the sum of theseries is indeed 1. Unfortunately, only afew of the rectangles can be shown. The I I I I II

33

How the Other Half Thinks

square has area 1. The shaded rectangle has area 1/2, leavingan area of 1/2 unshaded. The next rectangle fills half theunshaded area, namely, 1/4. That leaves an area of 1/4 that isnot covered by those two rectangles. The next rectangle cov-ers half that area, so has an area of 1/8 and leaves an area of1/8 uncovered. The rectangles continue forever, each half aswide as the rectangle to its immediate left. The area that iscovered by all the rectangles is 1, the area of the square, but itis also

11111

— + — + — + — + — + •••

Hence the sum of this series is 1. To be precise, as we addmore and more terms, we get sums that are closer and closerto 1.

From this fact we can obtain many more sums that willbe useful in a moment. For instance, say that we start withthe information that

11111

— + — + — + — + — +

Subtracting 1/2, the first term, from both sides tells us that

1111 1

— + —- + — + — + ••• = —

Subtracting the first term, 1/4, from both sides of this equa-tion tells us that

1 + J_ +JL + 1

A pattern is starting to show up: The sum, starting at anyterm, equals twice that term.

34

Win by Two

Finding the Average

Our detour through sums that are simpler than the sum

will help us calculate this sum, which is the one that ex-presses the average number of tosses before heads or tailslead by 2.

First, let us divide each term by 2, in order to have a littlesimpler sum to deal with. Once we find the simpler sum, wemust remember to multiply it by 2. The simpler sum is

1x5 +

To find this sum, we will use a tool that will come in handyin Chapter 3, "The Complete Triangle." We will add upnumbers in two different ways and then equate the twosums. The numbers will come from an infinite number ofendless sums.

Using the information obtained earlier, in the practicesection, we may write

11111

—+—+—+ — + — + ■ • ■ = 1

1111

— + — + — + — +

1 + _L + JL + . . = 1

-L + -L + . • = !

35

How the Other Half Thinks

Each horizontal line consists of a series of terms on the left ofan equal sign and their sum on the right. The display showsthe sums we get if we add the numbers left of the equal signshorizontally first.

This diagram displays the same idea pictorially.

= 1

= V2

= V4

= 1/8

1 X 1/2 + 2 X 1/4 + 3 X 1/8 + 4 X 1/16 + ...

Now add up all the numbers to the left and right of theequal signs vertically first, column by column. That is, addthem all by first adding up numbers that are directly aboveeach other.

36

Win by Two

The first column has one 1/2. The second column hastwo l/4s. The third column has three l/8s. The pattern willgo on through all the columns. Thus the sum of all the termson the left is

(±xl) +(lx2) + (lx3) + (-1x4) + (J-x5) +

On the right we have the sum

. 11111

1 + — + — + — + — + — + ■••

The sum of all of its terms after the first is 1. So its sum is1 + 1, or 2.

Since adding line by line will give the same sum as addingcolumn by column, we find that

1x1 + 1x2 + 1x3 + 1^,4

+ I 1 x 5 +

We double this (since we divided by 2 to simplify matters) toobtain the sum that equals the average number of tosses untilthere is a lead of 2. We finally have

1x2 + 1x4 + 1x6 + f^x8

+ I — x 10| + ■•• = 4

In short, the theoretical average number is 4. The experimen-tal average, based on 64 tosses, was 4.66. The two averagesare not far apart. Presumably, if we toss a penny thousands oftimes, the observed average would gradually move closer to4 and away from 4.66. In any case, our common-sensemethod yields numbers that are in reasonable agreementwith those from the tossed pennies.

37

How the Other Half Thinks

A Second Look at Volleyball

What has our common-sense approach told us about volley-ball games that are tied at 24 to 24? First, about half of themshould end with a score of 26 to 24. Our record of 64 gamesincluded only 24 with that score, 8 less than theory suggests.Second, our theory predicts that one quarter of the gameswill end after 4 points are played, in other words, with ascore of 27 to 25. This implies that three quarters of the 64games, or 48, will end quickly, with at most 4 points scoredafter the 24-to-24 tie. Only 36 ended that soon. Third, theaverage number of points will be 4 even though some gameswill last quite long. That's far from the average of 7.03 in the64 games.

The common-sense approach works fine for the tossedpenny, but its volleyball predictions seem far off the mark.Why should this be? Why do so few volleyball games end asquickly as our analysis suggests? It seems that the volleyballgames last longer than the pennies or our common-senseapproach advise.

Volleyball enthusiasts offer a convincing explanation. Ina rally, the receiving team has a much better chance than theserving team of scoring a point. The players know this, and ifthey win the opening coin toss, usually they choose toreceive rather than serve.

Even though the teams are evenly matched, at any givenrally the receiving team has an advantage, winning from 70 to80 percent of the rallies in men's games and about 55 percentin women's games. Because of this, there will tend to be longstretches where teams alternate in scoring, thus taking longerto achieve a 2-point lead.

The mathematics that takes into account this contrastbetween server and receiver is more complicated than the

38

Win by Two

approach we used, so we will not go into it. I will just statetwo of the conclusions that can be drawn from it. First, thatthe average number of points played after the tie is equal to"2 divided by the fraction of rallies the server wins." Thatfraction is in the range of 1/5 to 1/3. If neither the receivernor the server has an advantage, then the fraction is 1/2, andwe have the case examined in this chapter, represented by theflipped penny. Note that "2 divided by 1/2" is 4, in agree-ment with our calculations.

In some volleyball leagues a team must be serving to gaina point. If it is not serving and it wins a rally, it earns the rightto serve but does not score a point. The mathematics thatcorresponds to these rules is much more complicated thanour method. It turns out that if the teams are equallymatched and neither server nor receiver has an advantage,then the serving team will score the next point in 2/3 of thecases, though many rallies may be played before it earns thatpoint. Moreover, 2/3 of tied games will end as soon as possi-ble, with only 2 points played. Two ninths will end with only4 points played, and 2/27 with 6 points played.

I compared these theoretical numbers with the record ofthe national women's team. Of 54 tied games, 41 ended after2 points, compared to a predicted 36; 10 ended after 4 points,compared to an expected 12; 3 ended after 6 points, com-pared to a theoretical 4. Clearly the theory gives a prettygood approximation of reality.

OtherViews

The problem that we introduced through sports appears inother ways, such as in the study of wandering bugs or gam-bling. It is a part of probability theory and statistics called the

39

How the Other Half Thinks

random walk, which has been applied to epidemics, the stockmarket, and changes in the human population.

Imagine a bug who is free to travel between two parallellines that are 4 units apart, as shown here. (Any animalwould do, but, as in Chapter 1, bugs are most often called onto assist our intuition.)

-1

-1 2 3 4 5-

The bug starts at point S and then makes one of two per-mitted moves at random. In one move he goes 1 unit rightand 1 unit up. In the other, he goes 1 unit right and 1 unitdown. If he bumps into one of the two border lines, his tripis over.

His trip could be over in just two moves. This happens ifhe is unlucky and both moves are up or both are down. Butif one is up and one down, he is back to the initial line and histrip continues.

Assume that the bug travels at random, as likely to moveup as down. How many moves will he take, on average,before he bumps into a border line? We have already figuredout the answer, which is 4 moves of the type described.

The same problem arises in the study of gambling, one ofthe earliest applications of the theory of probability somethree centuries ago. Each of two gamblers has 2 chips. Before

40

Win by Two

every play each gambler puts 1 chip in the pot. The playersare equally likely to win and take the pot. What is the averagenumber of plays before one gambler has all the chips? Theanswer, once again, is 4.

The theory has been worked out for situations in whichthe gamblers start with other, even differing, amounts, suchas 3 chips and 5 chips. In this particular case the gamblingwill last on the average for 15 plays. More generally, the aver-age number of plays is simply the product of the number ofchips the two gamblers have at the start. I would hope thatsuch a simple formula has a simple proof, but I have neverheard of one.

The same problem appears when a gambler bets againstthe house. Say that he starts with 5 chips and wagers 1 chip ata time. Assume he has an equal chance of losing that chip orgaining 1 chip. He resolves to play until he is up to a total of8 chips or is wiped out. On the average, if he faces this situa-tion many times, he will play 15 times before his stake growsto 8 chips or else disappears.

A Remark on Endless Sums

In our study of volleyball or coin tossing, we showed that

+ I —x 101 + • • - = 4

This equation says that as we add more and more terms, thesum gets closer and closer to 4.

This suggests some questions not related to volleyball.

If we have an endless sequence of positive numbers thatare getting closer and closer to zero, what can we say about

41

How the Other Half Thinks

their sums as we add more and more of them? Do these sumsalways tend toward some fixed number? If they do, can wealways find that number, expressing it in terms of familiarnumbers, as we did with the series in this chapter?

Or could the sums get arbitrarily large, eventually grow-ing beyond any fixed number, even though the numbers weadd get smaller and smaller?

For instance, what can we say about the followingsequence?

11111

— + — + — + — + — +• • •

As we add more and more terms, the sums increase. Oneof two cases can occur. Perhaps the sums grow bigger andbigger, eventually exceeding 1000, then 1,000,000, and soon. After all, since we are adding positive numbers, this is apossibility.

On the other hand, the terms are getting smaller andsmaller as we move along the series. Perhaps the sums don'tgrow arbitrarily large, but instead they are approaching somenumber, as was the case with the series that arose earlier inthis chapter.

When I first met this series, whose terms are the recipro-cals of all the whole numbers, I computed a few sums. On thebasis of that information, I bet a fellow student that the sumsstayed fairly small, never growing beyond 13. I lost the bet.A simple picture shows that the sums get arbitrarily large.

In the figure below each term in our series is representedby the area of a rectangle of appropriate height and width 1.

1

1/2 1/3

' I Lj/4_V^V6_V^V8_Vg 1/1Q

42

Win by Two

The area of this staircase is the sum of the series, whetherinfinite or finite.

We now draw another staircase made up of one l-by-1/2rectangle, two l-by-1/4 rectangles, four l-by-1/8 rectangles,eight 1-by-1/16 rectangles, and so on, as shown here:

V2

~| 1/4 | 1/4 ■ 1/8 . Vb Vb Vb 1/16 1/1e ...

Our second staircase fits inside the first one thus:

The total area of the shaded rectangles is

1 2 4 8 16

— + — + — + — + — +

which is

11111

— + — + — + — + — +•••

Adding up l/2s, which go on forever, we can make sums aslarge as we please. Thus the shaded area is infinite. It followsthat the sum of the reciprocals of all the whole numbers,being even larger, is also infinite.

It isn't always easy to figure out whether a series of pos-itive numbers will have an infinite sum or a finite sum. Entirebooks are devoted to techniques for deciding. Moreover,once we know a series has a finite sum, it isn't always easy totell what that sum is, although we can calculate it to anynumber of decimal places we may choose.

43

How the Other Half Thinks

For example, it has been known for over two centuriesthat the sum of the reciprocals of all the square numbersis one sixth of the square of n, the perimeter of a circle ofdiameter 1:

11111 K2

— + — + — + — + — + • • ■ = —

The reasoning is quite ingenious. On the other hand, no onehas a formula for the sum of the reciprocals of all the cubes ofwhole numbers:

11111

— + — + — + — + — + • • •

It was our good fortune to be able to find the exact sumof the series that gave us the average number of tosses ofthe penny. That is a rare piece of luck.

44

CHAPTER THREE

The Complete Triangle

11 is hard to predict when or how a new invention or discov-I ery will eventually be put to use. This chapter, which con-cerns the labeling of dots by letters, offers an example.Developed to prove theorems in topology, the result has sincebeen applied in such varied topics as the fair division of anasset or cost among several people and the tiling of a polygonby triangles of equal areas. After we have developed the the-ory, we will describe some of these applications in more detail.

The Problem on a Line

Imagine a string of a's and b's that starts with an a and endswith a b. Here are two examples:

abaabbab and abbaaababbaab

The string can be short or long. What can be said about thenumber of times an a and a b are next to each other? This

45

How the Other Half Thinks

simple question begins a journey that takes us into a famoustheorem called Sperner's lemma.

The first of our two strings has five such pairs of a and b;the second, seven. I invite you to conduct your own experi-ments. If your bookkeeping is accurate, you will find that thenumber of such pairs, where a and b are next to each other, isalways odd. Why is this so? Before reading on, you mightcome up with your own reason.

Here is one explanation. I'll illustrate it with the firststring, abaabbab, and begin by spreading it out as an intervalon a line.

o o o o o o o o

abaabb a b

The interval is cut into seven shorter sections. Any sectionthat has an a at one end and a b at the other end we call com-plete. A complete section occurs when we have an ab or a bain our original string of a's and b's. So what we want to showis that the number of complete sections is odd. To do this,inside each section we place a pebble next to any of its endslabeled a.

c? o ^—o o V o

abaabb a b

We shall count the total number of pebbles in two ways,just as we added up a collection of numbers in Chapter 2,"Win by Two." First we look at the pebbles from the view-point of the sections. In an aa section there are two pebbles;in a bb section there are none. A complete section has exactlyone pebble. So, whether the total number of pebbles is oddor even depends only on the number of complete sections. Ifthe number of complete sections is odd, so is the total num-

46

The Complete Triangle

ber of pebbles. If the number of complete sections is even, sois the total number of pebbles.

Now we look at all the pebbles from the viewpoint of thedots, which are labeled a or b. There are no pebbles next to ab. Next to each interior a are two pebbles. Next to the dotlabeled a at the end of the interval is one pebble. All told, thetotal number of pebbles is odd.

Putting the two counts together shows that the numberof complete sections must be odd, so the number of times wehave an a next to a b in the string must be odd. This meansthat behavior at just the two ends of the interval—an a at oneend and a b at the other—influences behavior throughout theinterval. If both ends had been labeled a or both had beenlabeled b, there would be an even number of completesections. We summarize these observations by saying that ifthe number of a's at the two ends is odd, so is the total num-ber of complete sections. And if it's even, so is the totalnumber of complete sections.

There is another way of looking at the strings, one thatwill give us more information. Now we will distinguish twotypes of complete sections, an ab section and a ba section. Inan ab, the a is to the left of the b; in a ba the a is to the rightof the b. We'll illustrate this approach with the same string,abaabbab, but describe it in general terms.

Let's start with the string stretched out on a line thus:

abaabb a b

Starting at the left end, we walk along the interval until wemeet a b. When that has happened, we have just crossed an absection. Then we continue walking to the right until we meetan a. (If there are no more a's, we're done: In such a case thereis one ab section and no ba sections.)

47

How the Other Half Thinks

However, when we meet another a, at that point we willhave just walked across a ba section. Then we continue walk-ing until we meet another b. And so on. On such a trip we runthrough all the complete sections, alternating ab sections andba sections. Since the first and last sections we meet are ab sec-tions, there is one more ab section than ba sections. Since thesum of an integer and the next higher integer is odd, we knowthat when we add the number of ab sections to the number ofba sections, the total number of complete sections will be odd.

The walking argument gives us the same conclusion asthe pebble argument. However, it tells us a little more: Thereis one more ab section than ba sections. In a moment, as wemove up from the interval to the plane, we will again havetwo ways of approaching a problem. And, again, one will tellus more than the other.

So far we have looked at subdivisions of an interval, a one-dimensional object. Now let's go up one dimension and con-sider subdivisions of a polygon by triangles. At this point wewill need, in addition to a and b, the letter c. This is one of thefew occasions when we choose to go so far into the alphabet,but, as you will soon see, doing so takes us into a fascinatingworld.

Consider a polygon, as below. In this chapter a. polygonis a figure made up of straight pieces that form a circuit (or

The Problem for Polygons

loop). The term also refers tothe region that is boundedby that circuit.

Place a dot at each of thecorners, and then place somemore dots, at random, on the

48

The Complete Triangle

border and in the interiorof this polygon. The fig-ure that appears to theright illustrates just oneof the countless ways thatthis can be done.

Then, using the dotsas corner vertices, cut thepolygon into nonover-lapping triangles. (Thisoperation, too, can bedone in many differentways, even for a given setof dots.)

Next, label each dot a,b, or c in any way what-soever.

Depending on howtheir corners are labeled,there are 10 types of tri-angles that may appear in the polygon, as is shown below.

In only one of the 10 types do all three letters appear.Call such a triangle complete. Six types have two different let-ters, and three types have only one letter.

49

How the Other Half Thinks

The complete triangle has exactly one edge with the lettersa and b, a complete edge. (Recall that a complete edge is onewhose ends are labeled a and b.) The triangle with two as anda b has two complete edges; so does the triangle with two b'sand an a. The others have no complete edges. We summarizethis information below by placing a number inside each trian-gle to record the number of its complete edges.

c ac ba ab be c

The complete triangle is the only one that has an odd numberof complete edges—namely, 1. In a moment we will put thisfact to use in another pebble-counting argument.

Our polygon happens to have two complete trianglesand four complete edges on the boundary. I invite you tocarry out a similar count with a polygon and labeling of yourchoice. If you do the counting accurately, your numbersshould illustrate the following claim, which we will call thegeneralized Sperner's lemma:

If there is an odd number of complete edges on theboundary, then there is an odd number of complete trian-gles. If there is an even number of complete edges on theboundary, then there is an even number of complete tri-angles.

In short, the number of complete boundary edges and thenumber of complete triangles are both odd or both even.

50

The Complete Triangle

Emanuel Sperner (1905-1980) stated his lemma for trian-gles, the form he needed. In the 1928 paper where the lemmaappeared, he used it to obtain short and elegant proofs forsome deep topological theorems about the dimensions ofvarious spaces. (The lemma can be generalized to all dimen-sions. For instance, in the next dimension up, dimension 3,his lemma refers to a solid tetrahedron, bounded by four tri-angles, and it involves the letters a, b, c, and d. In dimension1, it concerns the interval, the case that opened the chapter.)

Proof

The pebble counting used for the interval, slightly modified,will show why the generalized Sperner's lemma is true.Instead of placing a pebble next to a dot labeled a, we place itnext to a complete edge, labeled ab.

Inside each trianglein the subdivision of apolygon, we place a peb-ble next to each com- bplete edge, as shown tothe right. Each trianglewill hold 0, 1, or 2 peb-bles. Only the completetriangles have an oddnumber of pebbles. So,whether the total number of pebbles is odd or even is deter-mined by whether the number of complete triangles is odd oreven.

That counting was done from the viewpoint of the trian-gles. Next, count the pebbles by looking at the edges alongwhich the pebbles lie. Along each complete edge on the bor-der, there is one pebble. Along each complete edge in theinterior of the polygon, there are two pebbles. These two

51

How the Other Half Thinks

types are shown to the left.Therefore the total numberof pebbles is odd or evenaccording to whether thenumber of complete bound-

Border edge Interior edge ar7 ed§es is odd or even" B7

comparing the two ways of

counting—by triangles and by edges—we obtain the general-ized Sperner's lemma.

Sperner's Special Case

Sperner, and many others since, used a very special case ofhis lemma, where the polygon is simply a triangle whosethree corners are labeled a, b, and c. In this case, we intro-duce dots on the border and in the interior of the triangleand use them to cut the triangle into smaller triangles. Labeldots that lie on the edge joining a and b either a or b at ran-dom. Dots on the edge joining b and c label either b or c atrandom. Label dots on the edge ca either a or c at random.Sperner's special lemma then asserts that there must be atleast one complete triangle among the smaller triangles thatlie within the original triangle.

We have already done the work to show that the lemmais true. First observe that ab sections on the boundary occuronly on the edge that joins the corners labeled a and b. Aswe saw at the beginning of the chapter, there is an odd num-ber of ab sections on that edge, for it is an interval in its ownright with ends labeled a and b. The two other edges of thetriangle have no ab sections. So the number of ab sectionson the boundary of the triangle is odd. It follows immedi-ately that the number of complete triangles is odd. Thatimplies that there is at least one complete triangle, for zerois an even number.

52

The Complete Triangle

In his 1928 paper, Sperner used this special case to estab-lish a theorem about three subsets (parts) of a triangle whosevertices are labeled a, b, and c. Call the three parts S(a), S(b),and S(c). These sets may be bounded by curves, or they couldbe much fancier, even resembling clouds of dust particles.Assume that S(a) does not meet the edge be, S(b) does notmeet the edge ac, and 5(c) does not meet the edge ab. Assumealso that each point in the triangle is in at least one of thethree parts. A point may belong to more than one set. Anexample of three such sets is shown here.

Suppose you are given a very small positive number d. ThenSperner's special lemma shows that there are three points inthe triangle, P, Q, and R, all within a distance d of each other,such that P is in S(a), Q is in S(b), and R is in S(c).

The proof is quick, what isusually dubbed a "one liner,"though such proofs usually take afew lines. Cut the given triangleinto equilateral triangles whosesides have length less than d.

Place a dot at each vertex ofeach triangle. Label each dot a, b,

or c according to which of the three sets it is in. For instance,if it is in S(a), label it a. If it is in more than one of the sets,choose one of the possible labels. It is not hard to check thatdots on the edge ab of the given triangle are labeled a or b.

53

How the Other Half Thinks

Similar statements hold for the other two edges. Since theconditions of Sperner's lemma for a triangle are satisfied,there must be a triangle in the subdivision with all threelabels. The corners of this triangle are within a distance d ofeach other and serve as the three promised points.

A Refinement

In the one-dimensional case, the interval with a at the left endand b at the right end, we saw that there is one more ah sec-tion than ha sections. That was a refinement of our first the-orem, which referred only to complete sections and didn'tdistinguish the two types of complete sections. There is asimilar refinement for our generalized Sperner's lemma.

First, there are two types of complete triangles. If wewalk around the border of a complete triangle in the order a,h, and finally c, we move either in a clockwise or a counter-clockwise direction. We may speak then of clockwise com-plete triangles and counterclockwise complete triangles, asshown here.

a c a b

Clockwise Counterclockwise

Now, imagine a polygon with dots labeled a, b, and c bywhich the polygon is cut into triangles. Then imagine walk-ing around the border of the polygon in a counterclockwisedirection. You may meet some complete edges. In some ofthese you will meet the a first and then the b. Call these ahedges. In some you will meet the b first and then the a. Callthem ha edges.

54

The Complete Triangle

The following turns out to be true:

The number of counterclockwise complete trianglesminus the number of clockwise complete triangles equalsthe number of ab edges minus the number o/ba edges.

(In our polygon on page 51 this checks out, for 1-1=2-2.)For instance, if there were, say, five ab edges and three baedges, there would be two more counterclockwise completetriangles than clockwise. Therefore, there would have to be atleast two complete triangles. Our original version of Sperner'slemma would not have told us that there has to be a completetriangle. It would only have told us that the number of com-plete triangles must be even since the number of completeedges (5 + 3) is even. But according to that version, we couldnot have ruled out zero, an even number, as the numberof complete triangles. I'll mention later an application thatrequires the refined version of the lemma.

We can prove this refinement by slightly altering thepebble-counting technique. Instead of putting down peb-bles, we put either a 1 or a -1 along each complete edge ofeach triangle. We place a 1 if, as we sweep out the trianglecounterclockwise, we meet a complete edge in the ordera first, then b, which we can call an ab edge. If we meetthe complete edge as a b followed by an a, we place a -1, likethis:

55

How the Other Half Thinks

Now we sum all the -Is and Is. We know that each counter-clockwise complete triangle contributes a 1; and each clock-wise one has a —1. Each of the other types contributes a totalof 0. Therefore, the total of all the Is and -Is is

the number of counterclockwise complete triangles minusthe number of clockwise complete triangles.

Then we add up all the Is and -Is from the viewpoint of thecomplete edges. Since an inner complete edge has a 1 and a-1, this sum is

the number of ab edges on the border minus the numberof ha edges on the border.

That shows why the refinement holds [since the two waysof adding all the Is and -Is must give the same sum].

A Constructive Proof

If there is an odd number of complete border edges, theremust be at least one complete triangle. The proof we gave forthis is what is called an existence proof. It shows that some-thing exists but doesn't tell how to find it. Often, for practi-cal computation, an existence proof is only tantalizing. Whatone may want is a constructive proof one that gives a proce-dure for finding the object that we know exists. Of course,this then raises more questions, such as, "How efficient is theprocedure?" "Is there a faster procedure?" "How fast can thefastest possible procedure be?" These are questions that acomputer scientist faces.

But let's get back to describing a procedure for finding acomplete triangle if there is an odd number of completeedges on the border.

"We pick a complete border edge and start a journey,which will take us from triangle to triangle, at the triangle

56

The Complete Triangle

next to that edge. If that triangle is complete, stop. We havefound a complete triangle. If that triangle is not complete, itsthird vertex is labeled either a or b, and the triangle hasanother complete edge:

Start

When the triangle is not complete, we cross the second com-plete edge into the triangle on the other side of that edge. Ifthat adjacent triangle is complete, we stop; our search is suc-cessful. If it is not complete, we continue the journey fol-lowing the same rule.We continue in this fash-ion, moving triangle bytriangle. Our journeywill stop either when weenter a complete triangleor arrive at a completeedge on the border, asillustrated here.

If we do not bump into a complete triangle, we repeat theprocedure starting at another complete boundary edge. (Sincethere is an odd number of complete boundary edges, there willstill be unused ones.) We continue sweeping out such paths.Each path that does not end at a complete triangle uses up twocomplete edges on the boundary: one at the start and one at thefinish. Since there is only a finite number of triangles, we willeventually have a path that meets a complete triangle. (Not allthe paths can end at the border, for then there would be an

Finish

57

How the Other Half Thinks

even number of complete edges on the border.) By the way, ifthere were only one complete edge on the border, our veryfirst path would find the complete triangle.

Note that this process not only provides a way of findingthe complete triangle, it also provides a second proof thatsuch a triangle exists.

Two Detours

Let me add two detours, ones that use the counting-two-ways technique.

If we draw a polygon and some dots, we can use the dotsin many different ways to cut the polygon into triangles.Below is an example in which a polygon is subdivided in twoways with the same dots.

In each of these polygons there are seven triangles. This illus-trates a general phenomenon, as you may check with a poly-gon and dots of your choice: The number of triangles will hethe same, no matter how you use a given set of dots to cut upthe polygon.

To see why, imagine any subdivision of a polygon basedon a choice of dots. Each triangle in the subdivision con-tributes three angles that total 180 degrees. (A proof of this isin Appendix A.) Therefore the total number of degrees of allthe angles in the subdivision is the product of the number oftriangles and 180.

58

The Complete Triangle

Now look at the angles from the point of view of thedots. At an inside dot the total of the angles meeting that dotis 360 degrees since they fill out a whole circle around thatdot. At a dot on the border but not at a corner of the poly-gon, the angles total 180 degrees. The sum of the angles at thecorner dots is completely determined by the polygon. (Wedon't need to know the value of this sum, just that it is thesame in both cases.)

Since the total of all the angles is determined by the num-ber of inside dots, the number of border dots, and the poly-gon, the total is the same for all subdivisions drawn with theaid of a given choice of dots. Since that total is also equal tothe number of triangles times 180, the number of triangles isdetermined by the dots and the polygon. (Appendix A devel-ops a formula for the number of triangles in terms of thenumbers of inside dots, border dots, and corner dots.)

My second detour concerns cutting the surface of asphere into curvilinear triangles. Imagine placing dots on thesurface of a sphere and then using them to cover the spherewith triangles. It turns out that there must be an even num-ber of triangles. I invite you to show this by counting pebblesin two ways. (Place three pebbles in each triangle, one alongeach edge.) Similarly, if you then label all those dots a, b, or cat random, there must be an even number of complete trian-gles. Pebbles will show this too. Or you could show it bytaking a trip across ab edges as we did earlier.

Applications

It is not known how Sperner happened to think of his lemma.But once discovered, it became a tool that anyone could call onwhen needed. When mathematicians see their discoveries putto uses they had never imagined, it cheers them and reinforces

59

How the Other Half Thinks

their faith that their work is of value. I'm sure Sperner, whenasked to participate in a 1979 conference, Numerical Solutionsof Highly Nonlinear Problems, was delighted to see his lemmaplaying a role in applied mathematics.

Over the years Sperner's lemma has been applied in a sur-prising variety of problems. In 1929, soon after the lemmawas published, three mathematicians, Knaster, Kuratowski,and Mazurkiewicz, used it to obtain a very short proof of atopological result known as Brouwer's fixed-point theorem,which went back to 1910. Roughly speaking, that theoremsays that if you have a flat piece of rubber in the shape, say, ofa square, and crumple it and stretch it and put it back withinthe area where it had been, then some point, called a "fixedpoint," is back where it started. For instance, if you justrotate the square 90 degrees about its center, the center is thesole fixed point. Brouwer's theorem has been applied in dif-ferential equations (part of advanced calculus) and the theoryof matrices (part of advanced algebra).

The first application of Sperner's lemma, generalized, ofwhich I am aware was published in 1970. Monsky provedthat it is impossible to cut a square into an odd number of tri-angles of equal areas. (It is not hard to cut it into any evennumber of such triangles.) In 1989 Kasimatis proved that if nis an integer greater than 4 and you cut a regular n-sidedpolygon into triangles of equal areas, then the number of tri-angles must be a multiple of n. (When n is even, the refinedversion of Sperner's lemma is needed.)

In 1987 Sperner's lemma was the basis of a proof bySchmerl, one of 14 different proofs of the following geomet-ric theorem: Assume that a rectangle is tiled by rectangles,each of which has at least one side whose length is a wholenumber. Then the tiled rectangle itself has at least one sidewhose length is a whole number.

60

The Complete Triangle

In 1995 Hochberg, McDiarmid, and Saks used Sperner'slemma when studying a certain type of labeling of the dots ina system of dots and edges. I'll illustrate their work by onespecial case.

Consider the diagram of dots,edges, and triangles to the right.There are 15 dots.

Label each of the dots withone of the numbers from 1 to 15,using each number once. This canbe done in many ways. One wayis the straightforward, orderlyway shown to the right.

Each edge has a number ateach of its two end dots. Thelargest difference between thesetwo numbers is 5, which occursseveral times; for instance, at theedge whose ends have an 8 and a13. Is it possible to number the dots in such a way that all thedifferences are at most 4? The answer is no, and Sperner'slemma plays a role in showing this.

In 1999 Su published "Rental Harmony: Sperner'sLemma in Fair Division." It begins: "My friend's dilemmawas a practical question that mathematics could answer, bothelegantly and constructively. He and his housemates weremoving to a house with rooms of various sizes and features,and were having trouble deciding who should get whichroom and for what part of the total rent. He asked, 'Do youthink there's always a way to partition the rent so that eachperson will prefer a different room?' "

This type of problem has a long history. It occurs wher-ever several people want to divide some benefit or chore

61

How the Other Half Thinks

fairly. As Su remarks: "Our fair division approach is based ona simple combinatorial lemma, due to Sperner. However, donot be fooled—this little lemma is as powerful as it is simple."

When he came up with his lemma, Sperner was notthinking about fair division, fixed-point theorems, cutting asquare into triangles or a rectangle into rectangles, or differ-ential equations. Like an explorer of some uncharted land orsea, he added to our knowledge, moving us another stepaway from all other species, expanding the tool chest and theoptions of our civilization. That is typical of scientific dis-covery, whether it grows out of curiosity or out of necessity.And no one can predict how the many discoveries still beingmade today will be used in the unforeseeable future.

62

CHAPTER FOUR

Slumps and Streaks

In 1993 the Los Angeles Dodgers won exactly as many base-ball games as they lost. During a season of 162 games, theywon 81 and lost 81. In this they resembled a penny tossed162 times. But how close is this resemblance? I wonderedwhether the way the wins and losses occurred also resemblesthe way a tossed penny behaves. For instance, do the runs ofconsecutive losses or consecutive wins resemble the runs ofheads or of tails one gets tossing a penny repeatedly? In anutshell, how random were the Dodgers' wins and losses?

To find out, I contacted the team's publicity office, whichquickly faxed me that year's record of wins and losses, gameby game. These are the data, where W stands for a win and Lfor a loss:

LWWLLWLLLLWWWLLLLLLWWLLWLWWLWWLLWLLL

WWWWWWWWWWWLWWLWWLLWLLWWWWLLLWWLLLL

WWWLWWLWLWLWLWLWWWLWLLLLWWLWLWLWLL

WWWLLLLLLLWWLLWWWWWWLLLWLLWWWLWLL

WLLWLWWLWLWWWLWLLLWLLLLW

63

How the Other Half Thinks

As you scan the record, you will see isolated L's and Wsalong with much longer blocks, even a block of 11 Wsand a block of 7 L's. A block of Ws we will call a streak,even if it has just one W. For a weak team such a block mayindeed be viewed as a winning streak. A block of L's of anylength is a slump. There are 40 slumps alternating with 40streaks.

To obtain an orderly overall view, we record the data interms of the number of slumps and streaks of various lengths.First, since slumps and streaks alternate, and the first block isa slump and the last is a streak, the number of slumps mustequal the number of streaks. That observation served as acheck on my bookkeeping:

Length

Number

Length

Number

of Slump

of Slumps

of Streak

of Streaks

1

20

1

20

2

10

2

11

3

4

3

6

4

1

5

0

5

0

6

1

6

1

7

1

7

0

8

0

9

0

10

0

11

1

The most common slump or streak is just 1 game long.Half the slumps and half the streaks are of that length. Theslumps or streaks of length 2 are about half as frequent.Together with those of length 1, they account for about threefourths of the blocks. Long blocks are rare, with only four ofthem containing more than 4 games.

64

Slumps and Streaks

Next let us lump the slumps and streaks together. Thenext table combines the previous two tables:

Length of Block

Number of Blocks

i

X

40

2

21

3

10

4

5

0

6

2

7

1

8

0

9

0

10

0

11

1

Out of the 80 blocks, exactly half have length 1, theshortest possible. About half as frequent are the 21 blocks oflength 2. Half as frequent again are the 10 blocks of length 3.Blocks of length 4 are half as frequent as blocks of length3. The few longer blocks are of fairly random lengths.

Recall that I picked the Dodgers of 1993 because theywon as many games as they lost. If we flipped a penny 162times, we would expect around 81 heads and 81 tails. Therewould be runs of heads and runs of tails. How closely wouldtheir frequencies resemble those we just tabulated for theDodgers? For instance, would there be about 80 runs?Would about half of them have length 1? Would the longruns be rare?

An Experiment

There is a simple way to find out. Toss a penny 162 times andsee what happens. Here are the results when I did just that.

65

How the Other Half Thinks

There were 77 heads and 85 tails:

Length of Number Length of Number

Block of Heads of Blocks Block of Tails of Blocks

1 22 1 22

2 11 2 5

3 5 3 8

4 2 4 3

5 0 5 2

6 0 6 0

7 0 7 1

8 0

9 010 1

Except for the large number of tails blocks of length 3,the data resemble the tables for the Dodgers. Combining thedata for tails and heads, as we did for wins and losses, yieldsthe following information about the blocks:

Length of Block Number of Blocks

1

44

2

16

3

13

4

5

2

6

0

7

1

8

0

9

0

10

1

There are 82 blocks for the penny, a bit more than the 80blocks for the Dodgers. In both cases the most frequentlength is 1, and there are very few long blocks.

66

Slumps and Streaks

Let us compare the average block length for the twocases. The Dodgers had 80 blocks. Since there were 162games distributed in these blocks, the average length of ablock is 162/80, which is about 2.025. For the pennythe average length is 162/82 since it had 82 blocks. That isabout 1.976.

These comparisons suggest that chance played a big rolein whether the Dodgers won or lost a game, that chancealone can generate long blocks, hence long slumps andstreaks. In other words, slumps and streaks are to beexpected, even though the skill of batters and fielders maynot change. That chance plays a role should come as no sur-prise. For instance, the difference between a home run and along fly caught at the fence may be just a few inches or a ran-dom puff of air.

A Common-Sense Approach

Experiments, whether with the aid of a baseball team or apenny, can only suggest conjectures. (A conjecture has moreweight than a mere guess, for it is based on substantial evi-dence.) With the data we have collected, we may make somepredictions about what will happen if a hypothetical penny istossed billions of times. Mathematics can deal most easilywith a rigid structure, such as arithmetic, or with the totallyrandom. Oddly, within absolutely chance events a strictorder can be discovered. However, a mix of the controlledand the chaotic presents a specially difficult challenge, for wethen face the problem of extracting the signal from the noise.It is the same as the challenge faced by a doctor diagnosing apatient or an engineer getting rid of background hiss in arecording. Luckily, in the case of our hypothetical penny, wewill deal with chance alone.

67

How the Other Half Thinks

On the basis of the data at our disposal, we can make afew predictions about how our penny should behave. First,about half the blocks should have length 1. About a quartershould have length 2. Long blocks should be rare. The aver-age length of a block should be around 2. If the theory wedevelop gives results much different from these, we wouldeither have to carry out more experiments or alter the theory.

It may turn out that chance alone could cause longstreaks and slumps. If so, then baseball players need not takethem so personally, feeling depressed in a slump or ecstatic ina streak. Similarly, a gambler enjoying a run of good luckshould not assume that someone above is taking an interest.

Imagine now an ideal penny, equally likely to land tails asheads. That means that if this penny is thrown trillions oftimes, it will come up heads on very close to half the tossesand tails on half the tosses. To distinguish this penny fromthe real penny that I tossed 162 times, I will denote heads bya and tails by b.

Our first question is, "What fraction of the blocks willhave length 1?" Or, more specifically, "If the ideal penny isflipped trillions of times, about what fraction of the blockswill have length 1 ?"

Rather than examining blocks that appear later in theimaginary experiment, we consider only the first block, for itis typical of all the blocks. A block is a block, wherever itmay occur. We are now asking, "What are the odds that thefirst block has length 1 ?"

Look closely at how a block of length 1 happens. Thefirst toss of the penny can show either tails or heads, but thesecond toss must be the opposite of that first toss. Since theideal penny is fair, the odds of being opposite is exactly onehalf. So we would expect half of the blocks to have length 1.This is in agreement with what we observed: For the

68

Slumps and Streaks

Dodgers, 40 of the 80 blocks had length 1; for the penny, 44out of 82. So far, so good.

To strengthen our insight, let us analyze that first blockanother way. In this second method, we list all the ways thefirst 2 tosses could turn up, and see which ones lead to ablock of length 1.

There are four equally likely cases:

aa, ab, ba, bb

In the second and third cases there is a head and a tail. Thatis, the second toss is the opposite of the first one, and a blockof length 1 forms. There are therefore two out of fourchances that the first block has length 1. Therefore, the oddsthat the opening block has length 1 is 2/4 or 1/2, in agree-ment with our first analysis.

What fraction of the blocks will have length 2? Again wefocus on the opening block. This time we must consider thefirst 3 tosses. There are eight possible ways they appear:

aaa, aab, aba, abb, baa, bab, bba, bbb

In the first and last cases, aaa and bbb, the opening block willhave length of at least 3. In the four middle cases, aba, abb,baa, and bab, the opening block has length 1. Only the casesaab and bba produce an opening block of length 2, that is,two cases out of eight equally likely cases. So the odds ofhaving a block of length 2 are 2/8 or 1/4.

We could reach the same conclusion a little more directly.To form a block of length 2, two things must happen. Thefirst 2 tosses must be the same, and the third must be differ-ent from them. In half the cases the first condition will hold.In half of those cases, in which the first condition holds, the

69

How the Other Half Thinks

second restriction also holds. The odds of both conditionsbeing fulfilled are a half of a half, or 1/4.

Next, what are the odds that a block has length 3? Againthere are 2 ways to answer. Using the long method, we couldmake a list of all 16 ways that the first 4 tosses can turn up. (Iurge you to do this.) Then see in how many of these cases ablock of length 3 forms. These are the cases aaab and bbba.That will give odds of 2 out of 16, that is, 2/16 or 1/8.

Or we could take a shortcut, as follows. To form a blockof length 3, three things must happen: The second and thirdtosses must be the same as the first, and the fourth must beopposite. The odds for each of these things occurring is 1/2.Therefore, the likelihood that all three conditions are met is1/2 X 1/2 X 1/2, which, as we would expect, is again 1/8.

In the case of the Dodgers, 10 out of 80 blocks had length3, which is exactly 1/8, or 12.5 percent. For the flippedpenny, it was 13 out of 82, or about 15.9 percent, slightlylarger than the theoretical 1/8.

In the same way we can show that the odds that a blockhas length 4 are 1/2 x 1/2 x 1/2 x 1/2, which is (1/2)4 or 1/16.More generally, the odds that a block has length n are just theproduct of n of the l/2s. No wonder a long slump or streakis rare—but they can occur.

The Average Block

The average block length for the Dodgers was 2.025 and forthe tossed penny, 1.976. What average would common sensepredict? We will figure out this theoretical average in two dif-ferent ways.

Recall how the average was calculated for the Dodgers. Itwas the fraction 162/80, where 80 is the number of blocks and162 the number of games. That number 162 is the sum of the

70

Slumps and Streaks

lengths of all the blocks. Remember that there are 40 blocks oflength 1, 21 blocks of length 2, and so on. Rewriting thenumerator, 162, of the fraction 162/80 in terms of these variousblock lengths, we conclude that the average block length is

(40x1) + (21x2) + (10x3) + (5x4) + (0x5)+ (2x6) + (1x7) + (0x8) + (0x9) + (1x10)

Rewrite this as the sum of 10 fractions:

iLx6 + JLx7 + Ax8 + Ax9 + JLx10

M

♦(

(Ax.;

M

The first fraction, 40/80, is the fraction of blocks that havelength 1. The next number, 21/80, is the fraction of blocks oflength 2, and so on. To calculate the theoretical average—without any experiments—we replace these fractions by thetheoretical frequencies we have just computed. The theoreti-cal average is then

1 . 1 _ 1 _ 1 „ 1 _

— x1 + —x2 + —x3 + —x4 + —x5 + •••

We carried out the same steps when analyzing volleyballgames in Chapter 2.

We now face an endless sum, which looks a lot like a summet in that chapter. To be precise, each term in this sum isexactly half the corresponding term in the sum already eval-uated. Since that sum was 4, the new sum is 2. In short, thetheoretical average is 2.

Both experimental averages of block lengths, 2.025 and1.976, are quite close to the theoretical average. This agree-ment reassures us that our analysis makes sense.

71

How the Other Half Thinks

There is an even shorter way to compute the theoreticalaverage. We imagine a huge experiment in which the hypo-thetical penny is tossed, say, a million times. How manyblocks would we expect?

As the penny is tossed, a new block starts whenever thepenny comes up the opposite of what it did on the preced-ing toss. The odds of this happening are 1/2. That meansabout 500,000 times in a million tosses. So there should beabout 500,000 blocks. The total of all their lengths is1,000,000. The average length of a block is consequentlyabout

1,000,000 _2

This is the same value that we obtained by summing an end-less series.

We have two completely different ways of finding theaverage: by the shortcut and by the series. From this we againconclude that

(lxl) + (lx2) + (lx3) + (^x4) + (^x5)+...=2

Of course we already knew this, but we now have a short,indirect way of obtaining the same result. By considering theaverage of certain random events, we managed to sum anendless series.

Just as we studied the slumps and streaks of a team, wecould analyze them for an individual batter. The mathemat-ics is more complicated because the chance of getting a hitdoes not equal the chance of getting an out. (According tothe Baseball Encyclopedia, the typical batting average in themajor leagues is about 0.255: a player will get a hit in about 1in 4 at bats.)

72

Slumps and Streaks

In the case of basketball this analysis has already beendone. The results were reported in 1985 in the journal Cog-nitive Psychology in an article titled "The Hot Hand in Bas-ketball: On the Misperception of Random Sequences" byGilovich, Vallone, and Tversky. Based on the performance ofthe Philadelphia 76ers and the Cornell University varsityteams, they concluded that the slumps and streaks of individ-ual players were close to what would be predicted on thebasis of chance alone. They advised basketball coaches, whobelieve in the "hot hand":

Passing the ball to the player who is "hot" is a com-mon strategy. It is also anticipated by the opposing teamwho can concentrate on guarding the "hot" player. Ifanother player, who is less "hot" on that particular day, isequally skilled, then the less guarded player would have abetter chance of scoring. Thus the belief in the "hothand" is not just erroneous, it could also be costly.

Endless series, under their official name infinite series,are common in the study of chance events and in suchvaried fields as economics, trigonometry, and physics. Theapplications in this and the volleyball chapter (2) are only asmall sample of their many uses.

73

This page intentionally left blank.

CHAPTER FIVE

Thrifty Strings

To measure the distance to Venus, scientists bounced aradar signal off its surface and clocked how long it tookthe signal to return. They knew that if they used a singlepulse, it would get lost in the prevailing static. Therefore, thescientists sent a string of pulses in a pattern that they couldrecognize even if part of the string became garbled. Thischapter develops the mathematics behind that pattern. At theend of the chapter I will describe other applications, some ofwhich we use daily without being aware of them.

We begin again with a simple question about strings ofa's and b's.

The Question

Before we can pose the question, we have to define someterms. Any group of consecutive symbols in a string we calla word. The length of a word is the number of symbols in it.

75

How the Other Half Thinks

A word of length 2 we call a couplet, or 2-tuplet. A word oflength 3 is a triplet, or 3-tuplet. A word of length 4, a quadru-plet, is then a 4-tuplet, and a word of length 5, a quintuplet, isa 5-tuplet. More generally, for any whole number ra = 2, 3,4, . . . , a word of length n we call an n-tuplet.The string

aababbaaaba

is itself a word of length 11. It contains 11 words of length1. It also contains 10 (overlapping) couplets, 9 triplets, 84-tuplets, and so on. Thus it has words of all lengths from1 to 11.

We start with the simplest version of the general question:

How long can a string be if no couplet in it appears morethan once?

Let's see how long a string we can build by adding one letterat a time. We might as well start with the letter a. Because weare only on the first couplet, the next letter can be either a orb. Let's use a again, producing aa. The next letter cannot be abecause then our string would become aaa where the coupletaa appears more than once. It is safe, though, to add b next,and obtain the string aab. This string contains the coupletsaa and ab.

For the fourth letter we can add either a or b withoutrepeating any couplet. Let's use a, getting aaba. The fifth lettercannot be a since then the couplet aa would be repeated. Norcan it be a b, for then the couplet ab would appear twice. Weshould backtrack and change the fourth letter to b and seewhat happens. We then have aabb. We can't add b becausethen the couplet bb would appear twice. Adding a is permissi-ble, though, and doing so gives us the string aabba of length 5,

76

Thrifty Strings

with no repeated couplet. You may experiment yourself tobuild other strings of length 5 with no repeated couplet.

If you try to construct a string of length 6 with norepeated couplet, you will be disappointed. To see why, notethat there are only four possible couplets of a and b. They areaa, ab, ba, and bb. In any string of length 6, each of the firstfive symbols in the string would be the first symbol of a cou-plet. That forces the string to contain five couplets. Becausethere are only four possible couplets of a and b, this means atleast one couplet must appear more than once as soon as thestring has five couplets (or six symbols).

Now that we have considered couplets, the next questionthat invites an answer is,

How long can a string be that has no duplicated triplet?

To find out, we experiment again, starting, say, with thestring abab. The next letter cannot be a, because the stringababa would contain the triplet aba twice. Choosing b givesno trouble, so we use it and reach ababb.

Next we can add either a or b. Choosing b gives us thestring ababbb. If we add b next, we will have the stringababbbb in which the triplet bbb appears twice. But we canuse a, obtaining the string ababbba. Putting b next wouldforce a repeat of bab, but we can use a, and we have thestring ababbb aa of length 8. The next symbol can be eithera or b.

If we choose b, we get ababbbaab. But then we are stuck,for if we add a, the triplet aba repeats, and if we add b, thetriplet abb repeats. So we back up and use an a instead of b,giving us a string of length 9:

ababbbaaa

77

How the Other Half Thinks

If we add a to this string, then we repeat the triplet aaa. Butwe can safely add b, obtaining a string of length 10 withoutrepeated triplets:

ababbbaaab

It turns out that any string of length 11 (or greater) willinevitably contain a repeated triplet. The explanation for thisis just a slight variation of the one we just gave for strings thathave no repeated couplet:

Imagine a string of length 11, composed of a's and b's,occupying the 11 places here:

Each of the first 9 symbols is the first symbol of a triplet inthe string. The final 2 symbols merely complete the lasttriplet. If there were no duplicated triplet in an 11-symbolstring, there would need to be at least 9 different tripletsmade up of a's and b's.

Let's make a list of all possible triplets of a and b to seehow many exist. We arrange them in dictionary order to besure we find them all:

aaa baaaab bababa bbaabb bbb

All told, in this "dictionary list" we found 8: 4 beginningwith a and 4 beginning with b. In short, we can create all pos-sible triplets by putting either a or b in front of each of the4 couplets we identified earlier. That means that the numberof triplets is twice the number of couplets—hence 2 times 4,or 8. We really didn't need to make the list; we could justhave multiplied by 2 the number of possible couplets.

78

Thrifty Strings

Since any string of length 11 would contain 9 triplets, atleast 1 triplet in it would have to be repeated. So the longest astring without repeated triplets can be is 10.

We have found a string that contains each triplet exactlyonce and a string that contains each couplet exactly once.These are examples of what we will call full strings. For agiven whole number n, a full string is a string that containseach w-tuplet exactly once.

We have found that there are full strings when n is 2 or 3.Is there a full string for 4-tuplets? For 5-tuplets? If so, howmany symbols would there be in them? I invite you to exper-iment with pencil, paper, and eraser.

From Strings to Wheels

Look at the full string for triplets that we have just found:

ababbbaaab

Note that the final couplet ab is the same as the opening cou-plet ab. This is not a coincidence. It will be true for any fullstring for triplets. Here is why: Imagine any full string fortriplets, ending, say, in ab, like this:

ab

We will show that the first couplet has to be ab also. In otherwords, we will show that the first triplet must always beeither aba or abb.

Our approach will be indirect. We will assume that neitherof those two triplets appears as the first triplet in the full string.From this we will show that there would then be at least threedifferent triplets that end in the couplet ab. Such a conclusionis nonsense because there are only two triplets that end in ab.

79

How the Other Half Thinks

If neither of these triplets, aba and abb, appears at thebeginning of the string, they must both appear later, some-where in ab. Then each has an immediate pre-decessor, overlapping it in the couplet ab. One is aab, and theother is bob. That tells us that the triplets aab and bob are notthe final triplet in the string. But the final triplet also ends inab. That would mean that there are at least three triplets thatend in ab. But we know that there are only two tripletsthat end in ab—namely, aab and bob. So our assumption thatthe opening couplet is not ab has produced a false statement.That forces us to conclude that the opening couplet must beab, the same as the final couplet.

The same reasoning shows that in any full string fortriplets, the first and last couplets will always be the same. Tosummarize, letpq stand for any one of the four possible cou-plets, aa, ab, ba, and bb. That means thatp stands for either aor b, and that q stands for either a or b. Using the letters pand q as substitutes for either a or b permits us to make gen-eral statements economically.

We see that any full string for triplets begins and ends withpq, as shown below. Since p can be either a or b, and q can beeither a or b, this string is short for four different possibilities:

pq pq

Because the couplets at the ends of this string are the same,we can bend the string into a circle. The figure below shows

80

Thrifty Strings

how this is done, first gradually forming a spiral, then figura-tively gluing the matching ends pq together so the two p'smerge and so do the two q's.

We can change any full string fortriplets into a wheel with eight sym-bols in this manner. For instance, thefull string for triplets, ababbbaaab,becomes the wheel shown here. (Readthe wheel clockwise, starting at theleftmost a.)

In this wheel you can start anywhere you want and runthrough all eight triplets one by one. With a mere 8 symbolsthe wheel lists all eight triplets. This is fewer than the 10 sym-bols of a full string and far fewer than the 24 (8 times 3) sym-bols that appear in our dictionary list of triplets.

We now have three ways to list the eight triplets of a andb: a dictionary list, a full string, or a wheel. Not only is thewheel the most economical way to proceed, but it also turnsout to be the most convenient to analyze, as we will soonsee.

A Closer Look

Before we go on to examine strings and wheels for quadru-plets, it would be prudent to take a closer look at whatwe have done with triplets. The fresh perspective we obtainwill give us a new tool for dealing with rc-tuplets for anyvalue of n.

What makes a full string so efficient is that it exploitsoverlaps. For instance, the first four symbols, abab, of ourfull string, ababbbaaab, records the triplets aba and bob,which overlap in the couplet ba. We can see all the overlapsof adjacent triplets in our full string by spreading the triplets

a ba

81

How the Other Half Thinks

out in a way that clearly displays how each triplet overlapsmost of the next triplet:

ababababbbbbbbabaaaaaaab

To describe this overlapping in detail, we introduce auseful notation. As we did a moment ago, we will use lettersother than a and b to stand for either of those two letters. Wecan then call the general triplet pqr. An overlapping tripletfollowing it would share the couplet qr. So it would have theform qrs. Here each of p, q, r, and s stands for either a or b.With this in mind, let's turn our attention to strings for 4-tuplets (quadruplets).

To begin, we count the number of 4-tuplets by using thesame method with which we counted the number of riplets.We can obtain all quadruplets by putting an a or b in frontof each of the 8 triplets. That tells us that there are twice asmany quadruplets as triplets, hence 16 of them.

How long would a full string for quadruplets need tobe? Each of the first 16 symbols in such a string wouldstart a quadruplet, and the final 3 symbols would completethe last quadruplet. The string would therefore have alength of 16 + 3. In other words, it would contain 19symbols.

Just as we showed that the final couplet in a full stringfor triplets is the same as the opening couplet, we could

82

Thrifty Strings

show that the final triplet in a full string for quadrupletswould always have to be just the same as the opening triplet.This means that the full string could be bent into a wheelwith 16 symbols. Before reading on, you may want to exper-iment by trying to make such a wheel. Even if you are notsuccessful, the practice will help you understand the follow-ing discussion.

Rather than just struggle until we manage to build sucha wheel, we will take our time and analyze what is going onin such a wheel. The insight we gain will help us treat wheelsfor much longer rc-tuplets, without any further thought orwork.

Imagine that in such a wheel the wordabbabbb

occurs. This part records the following four 4-tuplets:abba, bbab, babb, abbb

The first two of these 4-tuplets overlap in the triplet bba. Wecan record this overlap in a diagram, like this:

abba bbab *- o ►

bba

Next, let's look at the quadruplets bbab and babb. Theyoverlap in the triplet bab. We extend the diagram to includethis information:

abba bbab babb ► o ► o ►

bba bab

83

How the Other Half Thinks

The last two quadruplets in our seven-letter string, babb andabbb, overlap in abb. Here we display all the overlaps in thestring abbabbb.

abba

bbab

babb

abbb

obba

obab

o

abb

pqrs

Now let's take a completely fresh view of the quadru-plets and their overlaps. Instead of thinking in terms ofstrings, we now are involved with what we can pretend areone-way roads and towns. The towns are the 8 triplets, andthe roads are the 16 quadruplets. The figure is only a smallpart of a larger system of one-way roads and towns, with thetowns (the triplets) recording the overlaps of the roads (thequadruplets).

The quadruplet pqrs becomes a road that goes from townpqr to town qrs. Each triplet occurs as the final triplet of two

quadruplets and the initial triplet oftwo quadruplets.

Letting the letters p, q, r, s, t, u,and v stand for the letters a or b, wesee what the system of roads andtowns looks like near the town pqr:Each town is at a junction of fourroads, two roads that enter it andtwo that leave it. For example, thefigure at the lower left shows whatthe highway system looks like nearthe town abb.

The roads near the town aaalook a bit different. One of theseroads, aaaa, is a loop: This road both'babb * enters and leaves the town. The fig-

pqr

qrs

vpqr

84

Thrifty Strings

ure below shows the roads near this town. Similarly, theroads near bbb also include a loop. The only towns withloops are aaa and bbb.

baaa

aaab

aaaa

o

oaaa

But even at towns aaa and bbb, two roads enter and two leave.

The entire highway system of 16 roads and 8 towns isshown here:

baa

bbaa

bba

aab

aabb

abb

bbbb

This map of mythical towns and roads displays a great deal ofinformation. It shows all the overlaps of the 16 quadruplets.

85

How the Other Half Thinks

Glancing at a particular quadruplet, a road, we can easily readoff the 2 quadruplets that could possibly follow it in a fullstring. For instance, what could follow the quadruplet babb? Itends in the town abb. Since the roads abba and abbb leave thattown, either one could be the next quadruplet after babb. Thatcorresponds to either babba or babbb appearing in a string.

This fresh way of looking at strings and their overlaps willturn out to be the key to showing that full strings exist notjust for couplets and triplets but for quadruplets and so on.

Imagine that you travel about in this highway system,but you never go the wrong way on any one-way road. Forinstance, you could take a short journey, say, from bba tobaa, passing through the towns bab and aba along the way.You would travel on the roads

bbab, baba, and abaa

in that order. What does this mean in terms of strings ?

The first and second quadruplets (roads) overlap in thetriplet (town) bab. The second and third quadruplets overlapin the triplet aba. We display the three quadruplets and theiroverlaps in a staircase, as we had done with triplets:

bbabbabaabaa

Because of their overlaps, all three quadruplets could berecorded in the short string bbabaa.

The task of devising a full string that lists the 16 quadru-plets can now be rephrased in terms of the highway systemshown above. Keep in mind that we want to run through the16 quadruplets in such a way that adjacent quadruplets over-lap in a triplet.

86

Thrifty Strings

Consider a thrifty highway inspector who wants tocheck each road for potholes. To save on gasoline, she hopesto plan a trip that takes her over each one-way road in thelegal direction once only. Is there such a route? That is howthe question "Is there a string that lists all 16 quadrupletsonce each?" now reads. We have left strings and wheels farbehind and are now involved with finding routes through asystem of highways. Such systems are studied in the branchof mathematics known as graph theory, in which towns arecalled vertices and roads are called edges.

Finding a Route

Before we try to find a route for our highway inspector,we should check that the system comes "in one piece." Sheshould be able to get from any town to any other by alegal path. A few minutes' inspection of the map will showthat she can. However, we will show that indeed she cando this without looking at a picture. Moreover, our reasoningwill apply to the much more complicated highway systemsthat arise for 5-tuplets, 6-tuplets, and so on.

Say that the inspector is on the road pqrs and wants toreach the road tuvw. (As usual, the letters stand for the let-ters a and h.) The route described in the following stair-case will do the trick. It may not be the shortest routethat meets her needs, and it may have duplications, but thatdoesn't matter. It does show that she can get from anyroad to any other.

pqrsqrstrstustuvtuvw

87

How the Other Half Thinks

This route is shown here:

pqrs qrst rstu stuv tuvw ► o ► o >■ o ► o ;

qrs rst stu tuv

Let us illustrate this with a specific example in the high-way system shown on page 85. Say that the inspector wantsto go from the road bbba to the road abba. Our methodwould give her the route

bbbabbaabaabaabbabba

You may trace it out on the map and also find the inspector ashorter route from the road bbba to the road abba.

We are now assured that the inspector can get from anyroad to any other (while passing over at most three more

roads).

The Inspector Has aRoute over All Roads

To find the inspector a route tak-ing her over each road once, letus strip our highway system toits essentials, omitting the namesof the roads. The figure at the leftdisplays this stripped-down ver-sion, which is all we need for dis-cussing routes. To find a routeover all 16 roads, the inspector

88

Thrifty Strings

starts at any town of her choice, say the one labeled S in thefigure. She looks at her map and imagines starting to drive atrandom. Every time she enters a town, she chooses an exit.Since there are just as many exits (2) as entries (2) at eachtown, she won't get stuck anywhere except when she happensto bump into the town S a second time. (The first time shereturns to S, she will find an escape, but not the second time.)

In any case she wanders aboutuntil she gets stuck, which willalways happen at S. If she is lucky,she may have traveled over all 16roads. But her trip may have cov-ered fewer roads; for instance, shemay have journeyed over just 8sections, as shown to the right.That leaves her with still 8 roadsto inspect. Though she hasn'tcovered every road, at least shehasn't covered any road twice.

The loop at the bottom shecould include as a short side tripbetween the ones marked 3 and4. That is, she could alter her tripby covering 1, 2, and 3, thenwhirl around the loop, then goon to 4, 5, 6, 7, and 8. That stillleaves her with 7 roads to cover,but they can be included in sidetrips also.

Between 5 and 6 she couldadd a side trip covering 5 moreroads, as shown with the dottedlines.

89

How the Other Half Thinks

That leaves only the 2 roads inthe middle to cover. A short sidetrip between steps 1 and 2 sweepsthem out and the inspectorfinally has her perfect, economi-cal trip, shown by the numbers inthe figure to the left.

Such a complete inspectiontrip must end at the town where itbegins, S. All the other townshave as many exits as entrances,but beginning right after she hasstarted her trip, town S has onlyone exit available, though it still has two entrances.

Going back now to our highway system, we see that theinspector has inspected all 16 stretches of roadway in theorder shown in this staircase:

1 bbab2 baba3 ababAbabb5 abbb6 bbbb7 bbba8 bbaa

9 baaa

10 aaaa11 aaab

12 aaba13 abaa14 baab15 aabb16 abba

90

Thrifty Strings

You should not be surprised to see that the final quadrupletabba overlaps the first quadruplet bbab in a triplet—namely,the triplet bba, the town S. That just reflects the fact that thetrip must end where it starts.

Just for the record, this figure shows a a b

the wheel for quadruplets that corre-sponds to the inspector's trip. a

This wheel sweeps out all 16 quadru- bplets no matter where you start. a b b b

The Next Question

Now that we have shown that there are full strings for tripletsand quadruplets, we should see if there is a full string for list-ing 5-tuplets. Or, what amounts to the same, decide if there isa wheel that lists all 5-tuplets. It turns out that the work wedid with the inspector and the highway system for quadru-plets will help us settle the 5-tuplet case with little effort.

Just as there are twice as many 4-tuplets as 3-tuplets,there are twice as many 5-tuplets as 4-tuplets: 2 times 16, or32 5-tuplets. Reasoning as before would show that any stringwith more than 32 + 4, or 36, letters in it will have a dupli-cated 5-tuplet. To show that there is a string of length 36without duplications, let's do almost exactly what we didwith our mythical highway map for 4-tuplets. Not exactly,since the highway system would now have 32 roads and 16towns. Rather than draw such a complicated arrangement,we will simply describe it.

Each road now stands for a 5-tuplet of a's and b's, pqrst.Each such road goes from a town pqrs to a town qrst. Onceagain, two roads enter each town and two roads leave it.Moreover, using the same reasoning as before, we could showthat the inspector could travel from any road to any other.

91

How the Other Half Thinks

Without even drawing the system, we conclude that theinspector has a route that passes over each road exactly onceand ends at the town where the trip begins. That tells us, first,that there is a full string for 5-tuplets. Second, it assures usthat its final four symbols are the same as its first four sym-bols. From this information we conclude that there is a wheelwith 32 a's and b's in which every 5-tuplet appears exactlyonce.

We are now in a position to answer the general question,"How long a string exists where no n-tuplet is repeated?"

Recall that for the four couplets we made a string oflength 5. For the eight triplets our string had length 10.

Just as there are 2x2x2 = 23 = 8 triplets, 24 = 16 quadru-plets, and 25 = 32 5-tuplets, there are 2" n-tuplets, for eachtime we increase n by 1, the number of words of that lengthdoubles. A wheel for all the w-tuplets has 2" symbols. Astring for all the n-tuplets would have to be n — 1 symbolslonger in order to display all of the final w-tuplet. Forinstance, when n is 3, then n - 1 is 2, and the string has length8 + 2 = 10, as we saw.

Filling a Gap

We skipped over an important point in order not to interruptthe flow of our analysis. Now is a good time to take it up. Itconcerns the side trips. How do we know that the inspectorcan always add a side trip to a trip if she hasn't yet covered allthe roads? Could it happen that in a partial journey fromsome starting point S back to the same point she has used upall the roads adjacent to every town she has passed through,even though she hasn't covered all the roads? If that can hap-pen, then she will not be able to add a side trip.

92

Thrifty Strings

Here is how we can show that this will never happen:Imagine that the inspector's partial journey covers all theroads that touch each of the towns she has passed through.Then those towns and the roads joining them form a systemfrom which the inspector cannot escape. That means that noone could drive from any of those roads to reach an unin-spected road. But we showed that it is possible to drive fromany road to any other road. We conclude that as long as thereare uninspected roads, there will always be side trips theinspector can add to her trip.

Yet More General

What was it about the highway system that convinced us thatthe inspector could always find some route that would allowher to drive over each road only once? First, we used the factthat as many roads enter a town as leave it. Second, the systemconsisted of one piece: She could reach any road from anyother road. That's all, just an assumption about the small pieceof a highway system near each town, and an assumption aboutthe whole system forming one connected piece. We have reallyobtained quite a general insight into a property of certain high-way systems. Now let's apply this insight to extend our dis-coveries about strings that have no duplications.

For instance, what if we formed strings with the lettersa, b, and c? To be specific, say that we wanted to show thatthere is a wheel for 10-tuplets made with the letters a, b, andc. (There are 3x3x3x3x3x3x3x3x3x3 = 310 suchwords, just as there were 210 10-tuplets made with the let-ters a and b.) In this case we imagine a highway system inwhich each road is one of those 310 words. That's 59,049roads. Luckily we don't need to draw any of them. The

93

How the Other Half Thinks

39 9-tuplets of a, b, and c will be the towns. That's 19,683towns. Each road leads from its opening 9-tuplet to its end-ing 9-tuplet.

How many roads leave each town? For instance, howmany roads leave the town abaccbacc? That 9-tuplet is thefirst 9 symbols of 3 (not 2) 10-tuplets since we can add any ofthe 3 letters a, b, or c to it to make a 10-tuplet whose first 9symbols are the given 9-tuplet. So 3 roads leave each town.Similarly, 3 roads enter each town.

Since three roads leave each town and three roads enter it,the same number leave as enter. Moreover, just as we showedthat the system for quadruplets of a and b comes in one piece,we could show that the same holds for our much larger system.In fact, an inspector can go from any road to any other road bya route that passes over at most nine intermediate roads. That'ssurprising, given that there are so many towns and roads.

We can immediately conclude that the inspector of thisvast system does have a route that sweeps out each roadexactly once. That tells us that there is a wheel with 59,049symbols that lists all 59,049 10-tuplets of a, b, and c exactlyonce each.

We reached this conclusion almost without any effort. Wedidn't even have to draw anything or make any lists. Thedeeper we went into the original problem for triplets andquadruplets, the more general our thinking became. Cluttergave way to clarity. The concrete was replaced by the abstract,and the abstractions turned out to be extremely useful.

Finally, what if we wanted to design a route for a salesper-son rather than a road inspector? A salesperson would like aroute that passes through each town exactly once. This turnsout to be a much tougher problem. No one has found a simpleway to decide whether such a route exists in a given highway

94

Thrifty Strings

system. Checking all possible routes in a system with manytowns is not a simple task, even for a high-speed computer.

Applications

Wheels or strings of the type discussed in this chapter havehad many and varied applications. One of their more recentuses is long-range radar, such as the type that measures thedistance to the moon. Strings for 50-tuplets of a and b are fedin by a computer. Such strings go on for billions of symbolsbefore repeating any 50-tuplet. (A pulse of energy is used fora, and its absence for b.) Because the 50-tuplets are notrepeated, it is possible to identify exactly when a transmittedsignal, after bouncing off an object, returns.

How are such long strings produced? Not by the methoddescribed in this chapter, for it would be much too slow.Instead, algebra is used to provide a formula that gives thesymbols rapidly. The formula can easily be programmed fora computer. Some fascinating pure mathematics has beendeveloped to meet the challenge of finding the right formula.

Inside a computer there is a program for spotting and cor-recting errors in manufacture, known as a BIST, or a built-inself-test. This program and similar ones to help achieve reli-ability are also built into CD-ROMs and telephones. Electricalengineers call them shift register sequences, and they are con-structed with the aid of the strings described in this chapter.

Every time you make a call on your cell phone, you areidentified by a personal signature, which is a shift registersequence. This arrangement is known by its acronymCDMA, which stands for code division multiple access.

Because shift register sequences appear fairly random,they are also used to conceal secret messages. First, a message

95

How the Other Half Thinks

is translated into a sequence of pulses and no pulses, and thena shift register sequence is mixed into it. The receiver, know-ing which sequence had been added, removes it and recoversthe original message.

Certainly the first application of these strings occurred inthe poetry of India some time between 200 and 2000 yearsago. The 8 rhythms of 3 syllables all occur in this memoryword of 10 syllables:

ya ma ta ra ja bha na sa la gam

This is just a disguised version of the string abbbabaaab. Amark over a syllable stands for a heavy beat. The first rhythm,ya ma' ta', is light, heavy, heavy; the next is ma' ta' ra', heavy,heavy, heavy, and so on to the last, which is light, light, heavy.

Throughout this chapter we've examined arrangementsof symbols on a line without certain repetitions. A variationon this theme, arrangements of symbols in a rectangle, hasplayed a role in the remote control of robots.

Consider a robot free to move within a 3-by-9 rectanglemade up of 27 cells. Each cell contains one of two shapes thatthe robot is programmed to recognize. Call the shapes aand b. The robot moves right or left, up or down, but doesnot rotate. On its base is a 2-by-2 window that can sense four

exposed cells at a time and transmitthis information to the operator. Inorder that the operator can tellwhere the robot is located, all the 2-by-2 blocks in the 3-by-9 rectanglemust be different. They are in our rectangle, as you maycheck.

Of course, if we allow the robot to rotate, then thisdesign is no longer adequate. For instance, the operator

b

a

b

a

b

a

b

a

b

a

b

a

96

Thrifty Strings

couldn't tell if the robot were in the top right corner or thebottom left corner. We will leave such concerns for specialiststo face.

As we look back over the chapter, we may ask ourselveswhat mathematics we used. Not algebra, not geometry, noparticular fact that we may have picked up in school. Rather,we depended on just three important tools in the mathemat-ical style of thinking: common sense, careful attention todetails, and a willingness to be flexible. No wonder that thestudy of mathematics provides an ideal preparation for somany careers.

97

This page intentionally left blank.

CHAPTER SIX

Counting Ballots

Imagine an election in which there are two candidates, Annand Barbara. The ballots are in the ballot box and about tobe counted one by one. Barbara has more votes than Ann.What is the chance that Barbara stays ahead of Ann through-out the count? If we let the letter a stand for a vote for Annand the letter b stand for a vote for Barbara, this question willquickly lead us to investigate strings of a's and b's.

Let's start with a simple case in which there are three b'sand two a's. Here is a list of all the possible orders in whichthe five ballots can be pulled out of the box:

aabbbababbabbababbbabaabbbababbabbabbaabbbababbbaa

How the Other Half Thinks

You could make your own list to check that this list is com-plete. There are 10 possible orders.

If an a is drawn at the very start, Ann is ahead. Then thereis no chance that Barbara leads all the time.

If a b appears first and then immediately an a, Ann andBarbara are tied. Again there is no hope for Barbara to leadthroughout, no matter in what order the remaining ballotsare drawn, since no one leads in a tie. If Barbara is going to beahead all the time, then she must get the first two votes pulledfrom the ballot box.

These two observations eliminate the first seven stringsin the list. In the eighth, bbaab, Barbara loses the lead at thefourth ballot counted. Only in the final two strings, bbabaand bbbaa, does Barbara always maintain a lead.

Since in 2 of the 10 possible orders of counting the bal-lots, Barbara always stays ahead, we say that the likelihoodof her retaining the lead throughout the count is 2 out of 10,or 2/10, or 20 percent.

With many more votes—hundreds or thousands—a listof the possible orders would be so long we would not wantto write it down. If we felt ambitious, we might assign thetask to a computer, but even the computer may be reluctantto face so many possible strings and check in which ones theb's always lead the as.

Of course we could save time by not bothering to writeany string that starts with an a. In our list we can easily seethat 4 of the 10 strings begin with a. That is 4/10, or 40 per-cent of the strings. Sixty percent begin with b. It is amongthese latter strings that we find the strings in which Barbaraleads all the way.

In the case in which Ann has 10,000 and Barbara 15,000votes, there are 25,000 ballots in the box. We may not list allthe possible orders, but we can at least find the fraction of the

100

Counting Ballots

orders that begin with a. In those orders Barbara cannot pos-sibly lead all the way.

If you reach into the ballot box without peeking, youhave 10,000 opportunities to grab an a and 15,000 of grab-bing a b. That means the likelihood of plucking an a at thestart is 10,000 out of 25,000, or 10,000/25,000, which reducesto 10/25, and finally to 2/5, or 40 percent. To put it simply,"Two fifths of all the possible orders of counting the ballotsstart with a vote for Ann."

We don't know how many possible orders there are,but we do know that 2/5 of them start with an a and 3/5 ofthem start with a b. We could pause to figure out the fractionthat start with bb. And then we could calculate the oddsof the first three votes being bbb or bba. Matters wouldquickly get very complicated as we calculate the odds that Bar-bara is ahead throughout the first four votes, then for the firstfive. We would give up because the work would exhaust us.

Happily, there is a neater solution, another "one-linesolution," though the line may occasionally be rather long.Sometimes a one-line solution may require a paragraph; nev-ertheless, a one-line solution should be elegant and, in retro-spect, simple. This whole chapter is devoted to presenting theone-line solution of our voting problem. Once you read overthe solution, you will, I hope, agree that it could have beenexpressed in a few words, rather tersely perhaps, but clearlysummarized. As we will see, it depends on one delightfulgeometric insight. I call it "delightful" for it solves our prob-lem in a blinding flash.

Collecting Data

At this point, when we still have no idea what the answermay be, we do what mathematicians usually do in such sit-

101

How the Other Half Thinks

uations. We experiment, starting with the simplest cases.We will do that, record the data, and hope to find a pattern.With luck, the data may even suggest a way to analyze theproblem.

In order to discuss the cases, we introduce some nota-tion. The number of votes for Ann we will call N(a), whichwe read as "N of a." N(b) is the number of votes for Barbara.In our opening example N(a) is 2 and N(b) is 3. We also men-tioned the case where N(a) is 10,000 and N(b) is 15,000.

The simplest case is when Ann gets no votes at all—thatis, when N(a) is 0. In that case Barbara is always ahead in thecount. In numerical terms, there is a 100 percent chance thatBarbara stays ahead throughout the count.

The next case occurs when Ann gets exactly one vote,that is, when N(a) is 1 and N(b) is therefore at least 2, sincewe always are assuming that Barbara wins the election. Of allsuch cases, the simplest is the one in which Barbara gets justtwo votes. Here is the list of all ways the total of the threevotes can be counted:

abbbabbba

Only in the last of the three cases does Barbara stay aheadthroughout the count. In short, her likelihood of stayingahead is 1 out of 3, or 1/3.

The next case has N(a) equal to 1 and N(b) equal to 3.There are now four possible orders of the counting:

abbbbabbbbabbbba

102

Counting Ballots

Only in the last two cases does Barbara lead all the way. Thelikelihood of this is then 2 out of 4, which is 2/4.

The next case has N(a) equal to 1 and N(b) equal to 4, forwhich there are five possible outcomes:

abbbbbabbbbbabbbbbabbbbba

In this instance the likelihood of Barbara staying ahead is 3/5.

You may want to run through a few more cases whereN(a) is 1, just to be sure you have the feel of the problem anddata.

So far, this is the information we have gathered, includingthe case in which N(a) is 2 and N(b) is 3:

N(a) N(b) Likelihood

1 2 1/3

1 3 2/4 = 1/2

1 4 3/5

2 3 1/5

There's not much evidence here on which to base a conjec-ture. You may want to check the case in which Ann has twovotes and Barbara has four votes. But we will check the nextcase in which N(a) is 2 and N(b) is 5. There turn out to be 21possible strings or orders, listed here:

aabbbbb bbaabbb

ababbbb bbababb

abbabbb bbabbab

abbbabb bbabbba

103

How the Other Half Thinks

abbbbab bbbaabb

abbbbba bbbabab

baabbbb bbbabba

bababbb bbbbaab

babbabb bbbbaba

babbbab bbbbbaababbbba

To convince yourself that the list is complete, look carefullyat the two as. They methodically run through all their possi-ble locations, sweeping out the left column first. In 9 of the21 cases, Barbara holds her lead throughout the count. Oursummary list now reads:

N(a)

N{b)

Likelihood

1

2

1/3

1

3

2/4 = 1/2

1

4

3/5

2

3

2/10= 1/5

2

5

9/21 = 3/7

Before reading on, spend awhile inspecting these data. Whatseems to be a formula for the fraction? You will probablyspot the simple pattern. (To see this pattern, you will some-times have to use the unreduced fraction, sometimes thereduced one.)

It seems, judging by the information gathered so far, thatthe numerator of the likelihood fraction is the differencebetween N(b) and N(a)—that is, N(b) - N(a)—and that thedenominator is the sum of those two numbers, N(b) + N(a).In short, the likelihood of Barbara's staying ahead is simply

N(b) - N(a)

That is an educated guess, not an established fact.

104

Counting Ballots

Further Checks

You may want to check our conjecture by running somemore cases, for instance, when Ann has two votes and Bar-bara has six votes. In any event, it would be wise to stop anddo another case just to get a deeper feeling for the problem.

Another check is to see what the formula tells us whenAnn gets almost as many votes as Barbara. In this case the oddsof Barbara staying ahead throughout the count should befairly small. Does the formula support this assertion? WhenAnn gets almost as many votes as Barbara, N(b) - N(a) issmall. Therefore, the numerator in our formula is small andthe whole fraction is therefore small. That agreement with ourintuition gives us more confidence that the formula is correct.

We can also check our conjecture experimentally. We cancount the ballots one by one many times and see in whatfraction of the cases Barbara stays ahead. For instance, takethe case in which Barbara has 7 votes and Ann has only 3. Wemay use 7 red checkers to stand for Barbara's votes and 3black checkers to represent Ann's 3 votes. If you don't havecheckers, poker chips will do. In any event, put the 10"votes" in a jar, shake madly, and pull the votes out one byone without peeking. Record whether or not the b's stayahead all the time. Then do the experiment again and againuntil you have accumulated lots of data. In each case, if thea's ever catch up or lead, you can stop the count.

I did this experiment 50 times with poker chips. Barbarastayed ahead of Ann in 21 of the counts. How does this com-pare with our conjecture? In this case, N(a) is 3 and N(b) is 7.The conjecture predicts that the likelihood that Barbara willhold the lead throughout the count is

N(b) -N(a) 7-3 4

105

How the Other Half Thinks

In short, Barbara should stay ahead in 40 percent of thetimes that the count is made. Since I conducted the experi-ment 50 times, and 40 percent of 50 is 20, we would expectabout 20 of the trials to have Barbara always ahead. Theexperimental result of 21 out of 50 trials is so close to thetheoretical 20 that it gives further evidence that the conjec-ture may be right.

Another check is to see what the conjecture says whenAnn gets no votes at all, that is, when N(a) is 0. In that casethe formula becomes

N(b) - 0

which reduces to 1, or 100 percent. That agrees with ourobservation earlier that when Ann gets no votes, Barbaraalways has the lead throughout the count.

One more remark before we try to see whether the for-mula is correct. If Barbara leads Ann during the entire count,the very first ballot picked must be for Barbara. What is thelikelihood that this happens?

In the ballot box are N(b) + N(a) ballots. Of these, N(b)are for Barbara. So the odds of picking out a ballot for Bar-bara are

N(b)

Now, our conjecture that the likelihood that Barbara staysahead the whole count is

N(b) - N(a)

This fraction is less than the fraction N(b)/[(N(b) + N(a)]. Itshould be since "staying ahead the whole count" is less likely

106

Counting Ballots

than "getting the first ballot picked." That is further evidencein favor of our conjecture.

Searching for an Attack

The conjectured formula is so short and simple that thereought to be a short and simple explanation for it—especiallyif it is correct.

One way to try to explain it is long and complicated:First, calculate the total number of orders in which the bal-lots could be counted. In other words, work out a formulafor the length of the list of possible outcomes in terms of thenumbers N(a) and N(b). In the examples we treated, this waseasy because the lists were so short. Then we would try tocalculate the number of these strings in which Barbara leadsall the way. Dividing this second number by the length of thelist would give us the likelihood that Barbara stays aheadduring the whole count. Such a tedious approach is notattractive, especially in view of the simplicity of the formulawe are hoping to justify.

Another approach is to translate the problem into geo-metrical terms. That's what we did in the preceding chapter,where we began with a problem about not duplicating cer-tain words and ended up driving around highway systems.

A Bug Enters the Picture

This time let us imagine a bug walking about on an endlessline. The line is marked like a ruler:

• 3-2-1 0 1 2 3 • • •

1 1 1 1 1 1 1

The bug starts at 0. As the ballots are counted, he moves 1 unit

107

How the Other Half Thinks

to the left or right depending on whether the ballot is for Annor for Barbara. When an a is pulled out, he moves to the left 1unit. When a b is pulled out, he moves to the right 1 unit.

Say that the ballots are drawn in the order bbaba. Thenthe bug starts by moving to the right twice, then once to theleft, then once to the right, and finally once to the left. Hissuccessive positions are shown in the following figures asheavy dots.

3

-2

-1

0

1

2

3 • • •

1—

3

—i—-2

—i—-1

0

—I—

1

—i—2

—i

3 • • •

1—

3

—i—-2

—i—-1

—i—0

1

—i—2

—i

3 • • •

1—

3

—i—-2

—i—-1

—I—0

—I—

1

2

—i

3 • • •

1—

3

—i—-2

—i—-1

—I—0

1

—i—2

—i

3 • • •

1—

3

1

—i—-2

1

—i—-1

1

—I—0

1

—I—

1

2

1

—i

3 • • •

In this particular case the bug stays to the right of his startingposition, 0. That is the pictorial equivalent of saying, "Bar-bara stays ahead of Ann throughout the count."

We can now state our general ballot-counting problemgeometrically. A bug wanders on a line, starting at 0. In somerandom order he takes N(a) steps to the left and N(b) steps tothe right, where N(b) is larger than N(a). "What is the likeli-

I08

Counting Ballots

hood that the bug stays to the right of 0 throughout hisentire journey?

Unfortunately, diagrams like the ones we have just seengive us no deeper insight. They consist of many separate fig-ures, one for each ballot cast. The whole count is not shownin one picture.

There is another geometric approach, an approach thatdisplays the entire count in one figure. This approach alsomakes use of a bug, but this bug crawls about in a plane, notjust on a line.

We draw a pair of lines at a right angle to each other andmark them like a ruler. The horizontal line has the numbers0, 1, 2, 3, ... , while the vertical one also has those numbersas well as the negative numbers -1, -2, -3, . . . , as is shownbelow:

54321

-1-2-3-4-5

0 1 2 3 4 5 6

109

Counting Ballots

In any count in which Barbara is always ahead, the firstballot counted must be b. That means the first move of thebug must be upward, like this:

3210-1-2-3

12 3 4

The first ballot counted is b.

As we saw, the chance of the first ballot counted being bis given by the fraction

N(b)N(b) + N(a)

The likelihood that the first ballot is an a is

m

In that case the first step of the bug is downward, like this:

—\—i—i—1 2 3

The first ballot is a.

I I I

How the Other Half Thinks

The Geometrical View

When Barbara gets N(b) votes and Ann gets N(a) votes, whatdoes the bug's path look like, even if Barbara doesn't stayahead in the count?

First, the bug starts at the point S where the horizontal andvertical lines in the figure meet. Then the bug crawls about, butwith each step it goes 1 unit to the right. So it ends up N(b) +N(a) steps to the right. During his journey the bug goes up N(b)times and down N(a) times. Since N(b) is larger than N(a), thebug ends up above the horizontal line—in fact, N(b) - N(a)units above it. So we can draw the point where his journey ends.It is the point labeled F, for "finish," in this figure:

N(b) - N(a)

•F

N(b) + N(a)

The bug has many possible paths from S to F, depending onthe order in which the ballots appear during the count. Wewant to compute the fraction of those paths that stay abovethe horizontal line. Based on skimpy data, we suspect thatthis fraction is

N(b) - N(a)

However, at this point we are not sure our suspicion iscorrect.

112

Counting Ballots

A Clue

The fraction we just displayed can be written as the differ-ence of two fractions:

N(b) N(a)

As we saw earlier, the first of these two fractions represents thelikelihood that the first vote counted is b. Geometrically speak-ing, this means that the bug starts his journey with an upwardstep. The second fraction represents the likelihood that the firstvote is an a, and the bug moves downward at the start.

Barbara stays ahead of Ann throughout the count if thebug starts upward and never touches or crosses the horizon-tal line before he reaches F, the end of his path. To find thelikelihood of wandering in such a path, we start with the like-lihood that the path starts with an upward step and then sub-tract from it the likelihood that it then goes on to meet orcross the horizontal line. We are interested in the difference

N(b) _ the likelihood that the path starts upwardand meets the horizontal line

Look closely at the last two displays. They both begin withthe same fraction. If we can show that the two expressionsthat are subtracted are equal, our conjecture is true. Recallthat N(a)/[(N(b) + N(a)] is the likelihood that a path beginswith a downward step. So: "Why is the likelihood that a pathstarts with an upward step and then meets or crosses the hori-zontal line equal to the likelihood that a path starts with adownward step?"

The Key to Everything

The question is: "Why is the number of paths that start withan upward step and meet or cross the horizontal line equal tothe number of paths that start with a downward step?"

113

How the Other Half Thinks

At first glance we wouldn't expect any relation betweenthe two types of paths. Yet, if our conjecture is correct, thenthe two numbers must be equal. That is, the number of pathsthat start with b and meet or cross the horizontal line equalsthe number of paths that begin with a. I suggest that youexperiment with the case that N(a) is 2 and N(b) is 3 and see ifthe two numbers are equal before reading further. The left col-umn in the figure below shows the four paths that start with an

114

Counting Ballots

upward step and meet the horizontal line; the right columnshows the paths that start with a downward move.

Is there some easy geometric way to obtain the four pathsin the right column from the four paths in the left column? Wehope that there is some method and that the method works nomatter how many votes Barbara and Ann receive, as long asBarbara gets more than Ann does.

One tempting possibility is to reflect each path in the leftcolumn around the horizontal line. In other words, flip itaround that line. That certainly turns a path that starts withan upward step into a path that starts with a downward step.Unfortunately it also turns the finish point of the paths Finto a point other than F, namely, a point below the horizon-tal line. A good try, but no cigar. However, a slight change inthe reflection in the horizontal line will work.

The Modified Reflection

We didn't use the fact that the paths we are interested in notonly start with an upward step but that they touch or crossthe horizontal line at least once at a point other than thestarting point. Call the first such point C. The figure below

115

This page intentionally left blank.

CHAPTER SEVEN

Infinity

The most basic idea in mathematics is that of a "set." A setis any collection of objects, which are then called ele-ments of the set. The idea is so fundamental that we meet it inkindergarten or first grade. During the 1960s, in the era ofthe New Math, even the word itself was introduced thatearly. Maybe teachers don't use the word anymore, but theycertainly convey the idea, usually by drawing a loop arounda picture of two or three apples or bananas.

In daily life there are many synonyms for the word set,depending on the nature of its elements. We speak of a "flockof sheep" (not a "set of sheep") and a "herd of cows." Theword set is used in tennis; it consists of several games. The ele-ments of the "social set" are the wealthy people who partici-pate in debutante balls and fancy charity benefits.

In school we used finite sets to introduce whole numbers,which shows that the idea of a set precedes that of a number.(A set is finite if its elements can be counted—1, 2, 3,. . .,—and the counting stops.) In this chapter we focus on infinite

123

How the Other Half Thinks

sets, that is, the sets that are not finite, which are far more excit-ing than finite sets, as they offer paradoxes that violate ourintuition and quickly lead to contradictions that threaten ourfaith in common sense. Nothing in our experience with finitesets prepares us for the surprises that infinite sets offer.We start with a seemingly simple question.

A Simple Question

We will distinguish two types of strings made with the letters aand b, the finite and the infinite. A finite string stops. The stringababb is finite. A finite string can be short, perhaps consistingof just one letter, or as long as we please. There are an infinitenumber of finite strings. An infinite string goes on forever, suchas the string abababab . .., in which a's and b's alternate with-out end. There is an infinite number of infinite strings as well.

We now define two infinite sets whose elements arestrings. One consists of all of the finite strings made with a'sand b's. Call this seti^ for finite. The elements of the other setare the infinite strings, the strings that do not end. Call thisset I, for infinite.

As we said, both sets, F and /, are infinite, and this raisesthe question: are they equally infinite?

Our first reaction may be to say, "This is a ridiculousquestion. After all, infinite is infinite. Of course those twosets are equally infinite." That was the attitude until 1873when George Cantor (1845-1918) took the question seri-ously and answered it. His answer sent a shock wave throughthe mathematical community.

Back to Kindergarten

To understand Cantor's discovery, we must first review aconcept we learned in kindergarten. I am referring to the

124

Infinity

notion of "same-size sets," which underlies the definition ofthe whole numbers, 1, 2, 3, ... .

So let's pause for a brief refresher as we, in a sense,become children again.

Here we have a set of trucks and a set of bicycles:

Even before we understood the concept of "two" we couldhave shown that these sets have "the same size." All we needto do is draw lines or curves pairing each truck with a bicy-cle. In other words, we marry the elements of one set withthe elements of the other set: Each element in one set isuniquely paired with one and only one element in the otherset. All the elements in both sets get paired. That is what wemean by "having the same size." The next figure is likedozens we may have seen in kindergarten. It shows that thetwo sets have the same size:

125

How the Other Half Thinks

However, there is no way to pair off either of those sets withthe set of shoes in this figure:

No matter how you try to arrange the pairing, one shoe willbe left stranded.

Throughout this chapter we will use the phrase "samesize" in the precise sense we described. It does not mean

"same length" or "same area." Forinstance, the two line segments ABand CD in the figure to the left havethe same size but not the samelength. To show that they have thesame size in our sense, pair off eachpoint P on the segment AB with thepoint Q on CD that lies on the sameray through the point E as P does.We can apply the definition of two sets being thesame size to infinite sets without changing a word. Forinstance, consider the two sets below. One consists of all thewhole numbers and the other of just the even numbers.

/ 2 \

1 4 \

6

8

126

Infinity

We can pair each whole number with the even number twiceas large:

Having set up the pairing, we are permitted to assert that theset of whole numbers has the same size as the set of evennumbers. Even though we removed all the odd numbersfrom the set of whole numbers, what remains has the samesize as the original set. This is quite a contrast with thebehavior of finite sets. When we take away an element froma finite set, we no longer have a set of the same size. Instead,we obtain a "smaller" set.

What do we mean by smaller? We say that one set issmaller than another if it can be paired with part of the sec-ond set but it cannot be paired with all of that set.

We will stick to this definition of same size as we face thequestion, "Are the sets F and / the same size?" That question isreally asking, "Is there a way to pair off all the finite strings ofa's and b's with all the infinite strings of a's and b's?" If they arenot of the same size, then we should decide which is smaller.

Practice

Before trying to answer the question, let us show that the setF of finite strings has the same size as the set of whole num-bers, 1,2, 3, ... . We are obligated to devise a way to pair offthe two sets, element by element, to arrange a mass marriageof the whole numbers with the finite strings.

127

How the Other Half Thinks

It turns out that we can arrange such a marriage fairly sim-ply. First, arrange the finite strings in order of their lengths,and then, within a given length, in dictionary order. The listbegins:

a, b, aa, ab, ba, bb, aaa,...

This suggests how to marry the finite strings to the wholenumbers. Just match them, counting from left to right:

3,

b,

aa,

ab,

ba,

bb,

aaa,

T

1

2

3

4

5

6

7

The pairing continues forever, and we can now say that thetwo sets have the same size. In short, the set F has the samesize as the set of whole numbers.

Rephrasing the Problem

If the set / of infinite strings were the same size as the set F offinite strings, then it, too, could be paired with the set ofwhole numbers. The following figure suggests why this is so:

l F

We could just erase the set F, so to speak, and carry thepairing straight across from / to the set of whole numbers. In

128

Infinity

other words, we'd pair each infinite string, s, with the num-ber that is paired with the finite string paired with 5, thus:

1

In short, if / and F have the same size, then so do / and the setof whole numbers.

So we face this question: "Can the set of infinite stringsbe paired with the set of whole numbers?"

Let's begin by showing that the set / is at least as large asthe set of whole numbers. Here is a pairing of all the wholenumbers with some, but not all, of the infinite strings:

1 <=> abbbbbbbbb ...

2 <^> aabbbbbbbb ...

3 <^=> aaabbbbbbb ...

4 <^=> aaaabbbbbb ...

The whole number 1 is paired with the string that starts withone a and then continues with just b's. The number 2 ismatched with the string that starts with two a's and contin-ues with b's; 3 with the string that starts with three a's, therest being b's, and so on. This shows that / is at least as largeas the set of whole numbers.

The Answer

We are really asking, "Is there a complete list of the infinitestrings of a's and b's such that there is a first string, a second

129

How the Other Half Thinks

string, a third string, and so on?" If the answer is yes, such alist would look like this, where each dash stands for either ana or a b.

1

2

3

4

5

Every infinite string of a's and b's is supposed to appearsomewhere on the list.

George Cantor raised essentially the same question—that is, whether there is such a list of infinite strings—and in a letter of November 29, 1873, asked his friend,Richard Dedekind (1831-1916), whether he could answer it.Dedekind wrote back saying that he could not. On Decem-ber 2, Cantor replied:

I was extremely pleased to receive today your answerto my latest letter. I proposed my question to you for thefollowing reason. I had asked it several years ago and hadalways remained in doubt whether the difficulty which itpresents is a subjective one or whether it is inherent in thesubstance. As you write to me that you too are unable toanswer it I may assume the latter. Besides, I would like toadd that I have never seriously thought about it because ithas no particular practical interest for me and I fully agreewith you if you say that for this reason it doesn't deservetoo much labor. Only it would be a beautiful result.

A few days later, on December 7, he wrote Dedekind again:

Recently I had time to follow up a little more fully theconjecture which I mentioned to you; only today I believe

130

Infinity

I have finished the matter. Should I have been deceived, Iwould not find a more lenient judge than you. I thus takethe liberty of submitting to your judgment what I havewritten, in all the incompleteness of a first draft.

On December 7, 1873, Cantor had proved that /, the setof infinite strings in a and b, and the set of whole numbers donot have the same size, and with this discovery he inauguratedthe theory of infinite numbers. In his argument he used prop-erties of the number system. But later, in 1890, he devised amuch simpler argument, and it this one that I will present.

Imagine any list of infinite strings using the letters a andb, with a string matched with each whole number.

Cantor uses the list itself to construct an infinite string ofa's and b's that cannot be on the list. To do this, he begins bycircling the letters that appear along the diagonal, as shownbelow to the right. (Keep in mind that each dash stands for aletter, either a or b.)

Then he forms an infinite string out 1 Q

the top left corner. This string may or 3 —Q

may not appear somewhere in the list. 4 0

His next step is the key to what is 5 Q- -

nowadays called the diagonal method.

He operates on this string by changingevery a to a b and every b to an a. It is this string, which hederives by the switches, that he claims cannot appear any-where in the list. Call this string Cantor's string. If you thinkabout it for a couple of minutes, you will probably see whyCantor's string can't be any of the strings in the list.

Could Cantor's string, the one he formed by switchingthe letters along the diagonal, be the first string in the list?No, because it differs from that string at its very first letter,

I3I

How the Other Half Thinks

the one that he had circled. (Cantor's string may also differfrom that first string at other places as well.)

Could Cantor's string coincide with the second string inthe list? No, for it differs from the second string at least in itssecond letter.

Could Cantor's string happen to be the third string in thelist? No, for it differs from the third string at the third letter.

Similarly, Cantor's string cannot be the fourth, the fifth,or the sixth string, and so on. In short, the string he forms byswitching letters along the diagonal cannot appear anywherein the list.

Because the new string Cantor makes differs from any inthe list, that list is not complete. Therefore, there is no possi-ble way to pair off the whole numbers with the set / of infi-nite strings. It follows that the set of whole numbers and theset / do not have the same size, even though both sets areinfinite. Therefore, the sets F and / are not the same size, aswe set out to prove. In fact, / is larger than F, by an earlierremark.

With this discovery, Cantor founded the theory of infi-nite sets, eventually showing that there is an infinite numberof different sizes of infinite sets. Both this discovery and hisdiagonal technique have played a major role in the twentiethcentury in pure mathematics, logic, and computing theory.For example, the logician Kurt Godel (1906-1978) in 1931,using an argument reminiscent of Cantor's diagonal proce-dure, showed that there are mathematical truths in any math-ematical system containing ordinary arithmetic that cannotbe proved within that system. The mathematician Alan Tur-ing (1912-1954) used a variant of the same procedure toshow in 1936 that there could never be a universal computingmachine capable of duplicating the computations of everypossible computer.

132

Infinity

One question Cantor raised has inspired some of thedeepest research in the foundations of set theory. It can bephrased in terms of the set / of infinite strings, though it usu-ally is expressed in terms of the set of all numbers. This is hisquestion: "Is every infinite set of infinite strings the same sizeas the entire set of infinite strings or else the same size as theset of whole numbers?" Or, what amounts to the same thing,"Is there a level of infinity between the size of the set ofwhole numbers and the size of the set / of infinite strings ofa's and b's?" It turns out that the answer depends on theassumptions one makes about the basic properties of sets,and research is still being done on his question.

A Paradox

The notion of a set, which appears to be so simple and prim-itive that we really don't bother to define it, is more compli-cated than we may expect. For instance, Cantor's discoverythat infinite sets come in different sizes challenges our intu-ition and beliefs even if we follow every step of his diagonalargument and agree that there is no flaw in his reasoning.

We turn now to an episode that took place in 1902, whichshows the risks one runs when working with infinite sets.Recall that every set, finite or infinite, is composed of its ele-ments. For instance, the set of even whole numbers has theelements 2, 4, 6, 8, 10, 12,

The set of states in the United States has 50 elements.One of these elements is Wyoming. Wyoming is said to"belong to the set of states" or "Wyoming is an element ofthe set of states."

Another example of a set is "the set of all things that arenot shoes." This set is not a shoe. So it is an element of itself.It is certainly unusual for a set to be an element of itself; thus,

133

How the Other Half Thinks

a set that is an element of itself we will call unusual. If it is notan element of itself, we will call it a usual set. The set of statesis an example of a usual set, since it is not a state. The set ofeven numbers is a usual set since it is not an even number—itis not even a number.

Bertrand Russell (1872-1970) showed that strangethings happen when we consider the set whose elements areall the usual sets. Call this set S. Is S itself usual, or is itunusual? Surely it has to be one or the other. Let's see whichtype it is.

Could S be a usual set? If so, it is an element in the set ofall usual sets. But S is that set of all usual sets, so S is an ele-ment of S. That means S is an unusual set, for it is an elementof itself. Since S is now both usual and unusual, the assump-tion we made at the start must be wrong. That was theassumption that 5 is a usual set.

So it seems that S is an unusual set. That means it is anelement of itself, that is, it is an element of S. But the elementsof S are the usual sets. So S must be usual. Once again wehave nonsense, a set being both unusual and usual.

Whether we assume S is usual or we assume S is unusual,we get a clear-cut contradiction. Yet all we did was define acertain set, S. This is known as Russell's paradox.

On June 16, 1902, Russell wrote the logician GottlobFrege (1848-1925), describing his paradox. As he put it,"There is no class (as a totality) of those classes which takenas a totality, do not belong to themselves. From this I con-clude that under certain circumstances a definite collectiondoes not form a totality." Here "class" is another word for"set." Russell is saying that though we can define certain vastsets, we may not treat them as casually as we do simpler sets.

Frege responded on June 22, "Your discovery of the con-tradiction caused me the greatest surprise and, I would say,

134

Infinity

consternation, since it has shaken the basis on which Iintended to build arithmetic." ("Build arithmetic" is shortfor "provide a foundation for all of mathematics.")

On June 25, Russell wrote his wife, "I have heard fromFrege, a most candid letter: he says my conundrummakes not only his Arithmetic, but all possible Arithmetics,totter."

At the same time Frege added an appendix to a book ofhis which was already at the printer. Its opening paragraphwas, "Hardly anything more unfortunate can befall a scien-tific writer than to have one of the foundations of his edificeshaken after the work is finished." He went on, "This wasthe position I was placed in by a letter of Mr. Bertrand Rus-sell, just when the printing of this volume was nearing itscompletion."

Many years later, in 1962, when Russell was asked forpermission to publish his letter to Frege, he replied:

As I think about acts of integrity and grace, I realizethat there is nothing in my knowledge to comparewith Frege's dedication to truth. His entire life's workwas on the verge of completion, . . . his second volumewas about to be published, and upon finding that hisfundamental assumption was in error, he respondedwith intellectual pleasure clearly submerging any feel-ings of personal disappointment. It was almost super-human and a telling indication of that of which menare capable if their dedication is to creative work andknowledge instead of crude efforts to dominate and beknown.

Various mathematicians have patched up the axioms ofset theory in ways that avoid the pitfall of Russell's paradox.In one method it is postulated that there are two types of

135

How the Other Half Thinks

sets: those that are elements of some set and those that arenot. The details of how this theory is worked out are toomany and too technical for this little book. They would makeanother story.

Cantor's work deepened our intuition into the infinite, aconcept that had challenged philosophers going back toancient Greece. Russell, on the other hand, called attentionto the errors into which our intuition may lead us.

Research on infinite sets continues, as mathematicianstry to develop the basic assumptions about sets, from whichall their properties would follow by pure logic.

136

CHAPTER EIGHT

Twins

Some strings of a's, b's, and c's contain two shorter strings,or words, right next to each other that are identical. Forexample, the string cbabcabcac has two adjacent copies ofabc. As another example, baabc has two neighboring copiesof the short word a of length 1. On the other hand, the string

acbcabcbacb

has no such repetitions next to each other.

Call two identical words that are next to each other in astring twins. Perhaps "Siamese twins" may be more descrip-tive since the words are stuck together. A string that containsno twins we will call twin free.

How long can a string in the letters a, b, and c be if it istwin free?

This question and related ones were raised and answeredby the Norwegian mathematician Axel Thue (1863-1922) in1912. His motivation was simply the desire to know theanswer. As he explained at the beginning of his paper, "Forthe development of the logical sciences it is important to find

137

How the Other Half Thinks

large areas for speculation about difficult problems withoutany consideration of possible applications."

However, the question was destined to be asked severaltimes later. The American mathematician Marston Morse(1892-1977) raised it and related questions in 1921, when heused the answer to one of the questions in his study of themotion of a particle on certain curved surfaces. S. E. Arshon(a Russian mathematician who disappeared in a Stalinistreign of terror and died in prison around 1940), published hisanswer to the question stated above in 1937; he had heard thequestion at a conference in 1933. P. C. Novikov (1901-1975),another Russian mathematician, used Arshon's result in apaper published in 1959 that solved a famous problem inalgebra raised by the English mathematician W. Burnside(1852-1927) in 1902. Morse didn't know about Thue's work,and Arshon had no idea that the question had already beenanswered by Thue and by Morse. The applications of Morseand Novikov are too technical to be described here.

The history of Thue's problem illustrates two recurrentfacts about the practice of mathematics. First, discoveriesmade only to satisfy curiosity may many years later havetotally unexpected applications. Second, several mathemati-cians, working independently, may ask the same questionand come up with the same discovery.

Before we begin to consider Thue's question, we shouldpause to see what the answer is when we are permittedstrings made up only of a's and b's, instead of a's, b's, and c's.His question then becomes, "How long can a twin-freestring of a's and b's be?"

Such a string might as well start with an a. The next lettermust be b; otherwise, we would form the twins aa. So wenow have the string ab. The next letter must be a, and wereach aba, a string of length 3.

138

Twins

Can we add a fourth letter? We can't add an a since thenwe get an aa. But we can't add a b either, for then we wouldobtain abab, which consists of twins. We are blocked, and weconclude that the length of a twin-free string using just twoletters cannot be greater than 3. Later in this chapter we willuse the six twin-free strings on the letters b and c, which areb, be, beb, c, cb, and cbc.

Before Thue began his investigation he must have won-dered, "Could I make very long twin-free strings? Or is therean upper limit to their length? After all, the longer a stringgrows, the more chance there is that twins will form and I'llbe stopped."

Before reading further, you may want to stop and seehow long a twin-free string you can devise on the letters a, b,and c. Even a few minutes experimenting will help youappreciate the reasoning in the rest of the chapter.

The Method

The many solutions of Thue's problem offered over the yearsall depend on a technique called expansion. This methodinvolves the careful choice of three words, which I willdenote U, V, and W. Each of them is some string made up ofthe letters a, b, and c. (The ones that we will use later in thechapter are U = abcab, V = acabcb, and W = aebcacb.)

These three words must have the following property: Ifone starts with a twin-free string and replaces each a in it bythe string U, each b by the string V, and each c by the stringW, then the new longer string formed is again twin free.This procedure can then be applied to the longer string toproduce an even longer twin-free string. Applying theexpansion repeatedly would yield twin-free strings as long aswe please.

139

How the Other Half Thinks

To illustrate the process, assume that U is aba, V is cba,and W is bcb. If we apply the process to the string bacb, weobtain the string

cba aba bcb cba or cbaababcbcba

The only catch is finding the right words U, V, and W. Thechoice in the example is not right since it replaces a twin-freestring with one that has twins—in fact, four of them, aa,abab, bcbc, and cbcb.

My Search

I thought that before reading what various mathematicianshad found, I should spend a little time trying to find wordsU, V, and Wthat work. If I were lucky and happened to findsuch a triple, then I wouldn't need to read what others haddone. (Sometimes it's harder to understand someone else'ssolution than to find a solution yourself. In the first case youhave to deal not only with the mathematical substance butalso with the idiosyncrasies of another person's perspectiveand writing style.) If I didn't find such a triple, U, V, and W,at least I would be better prepared to read and appreciate thepapers that describe three words that do the job.

I wanted to find three words U, V, and W such that whenI replaced a, b, and c throughout any twin-free string by U,V, and W, respectively, I obtained another twin-free string. Iwill call the initial string the original string and the longerstring obtained by the replacements, the expansion, orexpanded string.

I looked for three short words. For convenience I nar-rowed my search to the case in which they all have the samelengths.

140

Twins

In the simplest case of interest, U, V, and W all havelength 2. I decided to assume that U = ab, since at this pointin the construction, a, b, and c all play the same interchange-able roles.

With this choice of U, both V and W must begin with aor c and end with b or c. (If, for instance, V begins with b,then UV contains the twins bb.) There are therefore fourpossibilities for V and for W: ab, ac, cb, and cc. Both ab andcc are immediately ruled out: We already have U = ab, and ccconsists of twins. Thus V and W are each either ac or cb.Since there are only two possibilities, one is V and the otheris W. I decided that I may as well assume that V = ac and W =cb. Then VW = accb, which includes twins. This showed thatU, V, and W cannot all have length 2.

I spent a few more minutes ruling out the case in whichthe three words all have length 3.

At that point I felt that the problem was certainly inter-esting, and I decided to do a little more experimenting.Rather than trying to find three suitable words of length 4,1tried some promising choices of U, V, and W. For instance,

U=ab, V=acb, and W= acabcb

None of these contains twins. Even better, none of the casesin which two of them are adjacent—UV, UW, VU, VW, WU,and WV—includes twins, as is easy to check. Unfortunately,UVW does, as it contains bacbac:

U V wab acb acabcb

I had done enough to see that finding a suitable U, V, and Wis not a trivial task. Moreover, I had a better feeling for the

141

How the Other Half Thinks

problem and was ready to appreciate the solution. I knewwhat obstacles had to be overcome.

The Solution

The simplest solution I found appeared in a paper of P. A. B.Pleasants in 1970, in which he considered several relatedproblems. This is his choice of three words:

U=abcab, V=acabcb, and W = acbcacb

I will call these three particular words blocks. They havelengths 5, 6, and 7. As a result, when an expansion is madewith their aid, the expansion will be more than five times aslong as the original string.

Pleasants' argument doesn't even use arithmetic. Instead,it depends on common sense and attention to details. Followthe steps carefully. The proof is an instance of proof bymeticulous bookkeeping.

Let us illustrate the procedure before we show that italways transforms a twin-free string to another twin-freestring. We begin with any twin-free string. For the sake ofsimplicity, we choose the string a of length 1. Expansionreplaces a by

U= abcab

Next, we repeat the procedure, so that abcab now plays therole of the original string. Replacing a by U, b by V, and c byW gives us

abcab

\^ \^ \^ \^ \^

abcab acabcb acbcacb abcab acabcb

142

Twins

It is not as easy to check that this expanded stringof length 29 is twin free just by eyeballing it. Each of thetwins could have any length from 1 to 14. Even a seeminglythorough search may fail to spot any twins (if there are any).

Expansion of our string of 29 symbols using U, V, and Wwould produce a string of more than 150 letters, much toolong to be easily checked by eye. Showing that expanding atwin-free string with the aid of these blocks always producesanother twin-free string requires careful attention to details.

A quick glance shows that the three blocks U, V, and Ware twin free. That is encouraging. Also, the six cases formedof two different blocks—namely, UV, UW, VU, VW, WU,and WV—are also twin free. For instance, inspection showsthat there are no twins in

UV= abcabacabcb

You may want to check the other five cases.

We must show that no matter how long an original twin-free string may be, the substitution of U for a, V for b, and Wfor c produces another twin-free string. Clearly, we must getsome insight into those three blocks in order to establish thisproperty. We can't write down all possible strings and checkthem by inspection.

Remarks on the Three Blocks

Each block begins with a and ends with b. Each block con-tains two as, a front a and a rear a. Each block is composedof two sections that begin with a, which we call a front sec-tion and a rear section.

All told, there are six sections. Each section consists of ana followed by one of the six twin-free words made with the

143

How the Other Half Thinks

letters b and c. These six words using b and c we call tags.There are three front tags in the front sections and three reartags in the rear sections.

The six tags are all different. Front tags end in c; rear tagsend in b. It follows that as you run through the a's in theexpansion of a twin-free string using these blocks, the lettersthat precede the a's alternate . . . b, c, b, c, b, . . . .

It is easy to decide whether an a in an expansion is a fronta or a rear a. Just look at the letter immediately left of it. Ifthat letter is b, then the a is a front a. If that letter is c, thenthe a is a rear a.

Outline of the Proof

We will prove that the expansion of a twin-free string byPleasants' three blocks yields another twin-free string. Forconvenience we will break the argument into three cases. Ineach case we will denote a pair of twins by 77* (tee and teestar). T and are twins, with T* the same word as T. Wegive the twins different names in order to be able to distin-guish them in the following discussion.

First, we will show that the expansion has no long twinsT and By long twin we mean a twin in which at least twoa's appear. In this case, T, and hence is long enough tocontain a complete tag. Second is the case in which T hasexactly one a. Third, Thas no a's. Note that in the last twocases the twins are quite short. In the second case T has nomore than six letters; in the third, no more than three letters.

The Proof

We begin the proof by analyzing the case where the twins arelong. Assume that in the twins 77*, T has at least two a's.

144

Twins

First, consider the special case in which T consists of blocks.That implies that the first letter in T is a front a. T and aremade up of the same blocks in the same order. The followingfigure illustrates the typical case:

T T*

u

V

u

w

u

V

u

w

These twins would come from the expansion of the part ofthe original string shown here:

a

b

a

c

a

b

a

c

There are then twins in the original string. But since the orig-inal string has no twins, an arrangement such as that shownin the first figure cannot occur.

We see therefore that the expansion of a twin-free stringhas no twins TT* such that T (hence T::") consists of completeblocks.

The case of long twins TT*, in which T does not consistof complete blocks, is more interesting. The twins in this caseappear as shown in the next figure. It shows the case in whicha twin contains two blocks; a twin could have any number ofblocks.

■* T *"*

T *■

block

T begins with just part of a block. Thus T* does too.That forces Tto end with just part of a block, and hence T*also.

145

How the Other Half Thinks

We will show that if there are twins of the type shown inthis figure, then there are also twins of the type already con-sidered, that is, twins that consist only of complete blocks.That simpler case we have already shown is impossible.

Recall that T has at least two a's. We must examine thesituation shown below, in which the first two a's in T (hencein T* also) are shown.

— T

— T »-

— a a —

|—a a —

There is a tag between the two a's shown in T. It ends ineither b or c. Consider first the case in which it ends in b—that is, it is a rear tag. It is part of a block, denoted B in thenext figure, that extends beyond T. The same block, denotedB:'% contains the left end of T* and extends to its left into T.

T T*

B B*

a -

-a — b

a

a -j— a — b

a

P Q R Q* R*

PR and RR* are identical and made of blocks

Consider the part of Tnot in B or B*, labeled QR. It is madeup of complete blocks. The same holds for the correspondingpart of T*, labeled Q::"i?:;". QR and Q*R* are identical stringsmade up of the same blocks.

Inspection of this figure then shows that the string PR isidentical to the string RR*. Therefore they are twins. More-over, they are composed of complete blocks. As we alreadysaw, this cannot happen in the expansion of a twin-freestring.

146

Twins

That takes care of the case in which the tag between thefirst two a's ends in b. The case in which it ends in c is simi-lar, and you may want to run through it. In that case the newtwins formed, which consist of complete blocks, are shiftedto the right instead of to the left.

We conclude that in an expansion of a twin-free stringthere are no long twins—that is, twins TT* where T has atleast two a's.

No Short Twins

Two much easier cases remain, in which a twin has one a ornone at all.

Take first the case in which Thas exactly one a. Of courseits twin, T*, also has exactly one a, as shown:

The two a's are much nearer each other than shown in thefigure since at most three letters separate them.

If a is not the first letter in T, it is preceded by b or c.The second a is then preceded by c or b, respectively, sincethe letters preceding the a's in a string made of blocksalternate. Thus T:;" is not the same as T. It follows that amust be the first letter of T, and we have the arrangementshown here:

147

How the Other Half Thinks

Could the two a's come from just one of the blocks, U =abcab, V = acabcb, and W' = acbcacb? It takes only a minuteto rule out any such possibility. For instance, if they bothcame from U, the figure would look like this:

The letter to the right of b in T:;" would be a front a, whichviolates the assumption that a twin has only one a (and thefact that T* is identical to 7). The blocks V and W can beruled out just as quickly.

Could the a's come from different blocks? In that casethe a in T would be a rear a and the a in would be a fronta. T would be the back section of a block. The diagram isshown here:

v-

a

Y

block

Y

block

That means that the rear tag that appears in Tmust be an ini-tial part of the front tag of a different block. Inspection of U,V, and W shows that this is never the case. In short, the caseshown in this last figure cannot happen. This disposes of allcases in which a twin has exactly one a.

Finally, what if Thas no a's at all? The picture in this caselooks like this:

Again, the neighboring a's in theT T* figure are really much closer than

they look since at most three letters

I I separate them. T consists of at most

148

Twins

one symbol, and so must T:;". Therefore TV' is one of aa, bb,and cc. None of these occur because the blocks have no suchtwins, nor does a pair of adjacent blocks.

This completes Pleasants' reasoning and shows that theexpansion of a twin-free string by the three chosen blocks isagain twin free. Repeated expansions provide twin-freestrings as long as we desire.

Questions

Typical of many mathematical discoveries, the proof we justfinished raises still more questions. If ignorance is measuredby the number of questions we can't answer, then, as we willsee, we are more ignorant after the proof than before.

How many strings using the letters a, b, and c, of eachgiven length, are twin free? Here is a table that shows the num-ber of twin-free strings of each length up through length 24:

Length Number of Strings Length Number of Strings

1

3

13

342

2

6

14

456

3

12

15

618

4

18

16

798

5

30

17

1044

6

42

18

1392

7

60

19

1830

8

78

20

2388

9

108

21

3180

10

144

22

4146

11

204

23

5418

12

264

24

7032

The numbers grow rapidly, but not wildly. Note how theratios between successive numbers behave. For instance, we

149

How the Other Half Thinks

have, approximately, 4146/3180 = 1.304, 5418/4146 = 1.307,and 7032/5418 = 1.298. Perhaps, as more values are calcu-lated, the ratios will approach a number near 1.3. If so, whatis that number? Could it be 1.3 itself?

Is there a different way to construct long twin-freestrings? A way that could be programmed for a computer? Away that would manufacture such strings letter by letter? Itried several approaches, described in Appendix B. One ofthem produced a string using four letters with length over 7million, at which point I shut down the computer.

The computer presented data that suggest new questionsand hunches, but it did not provide answers. However, with-out the aid of the computer, I wouldn't even have had data onwhich to base the questions. The computer is to mathemati-cians as a telescope is to astronomers or a microscope is tobiologists. It magnifies the power of the researcher. It mayexhibit a counterexample that refutes a theory, but it does notcreate theories or proofs.

A Bit of History

As I mentioned earlier, several mathematicians had solvedThue's problem, some unaware of earlier work, some awarebut offering different solutions. Pleasants, whose paper con-tains several other results, was clearly unaware of the detailsof Thue's solution.

In an e-mail I asked Pleasants how he found his threewords. "Just elementary messing about," was his reply. Hecontinued:

The problem came from a sheet of research problemscirculated among Cambridge mathematicians. I knew theanswer was known but didn't know what it was. Having

150

Twins

found it myself, I was encouraged to go on and try therelated unsolved problem that was the main subject ofmy papers.

Redoing something that's known can draw you intoa problem so that you can move on to something that'snot known. If you just read what someone else has done,you think it's so impressive and complicated youcouldn't possibly improve on it. Ignorance is a powerfultool for a mathematician. Maybe that's the advantageyoung mathematicians have.

After I understood Pleasants' solution, I thought itwould be interesting to see how Thue solved the same prob-lem in 1912. His solution, which is quite different fromPleasants', occupied a few pages hidden in a 67-page paper. Itis sketched in Appendix B.

Imagine my surprise to see that Thue had used the verysame blocks—abcab, acabcb, and acbcacb—that Pleasantshad chosen. That both, independently, used the same threeblocks suggests that these particular blocks may be the short-est possible. A. Capri in 1983 proved that they are indeed theshortest in the sense that their total length, 5 + 6 + 7 = 18, isminimal.

However, the three blocks abc, ac, and b come close totransforming twin-free strings to twin-free strings, as M. Hallproved in 1964. If we always replace a by abc, b by ac, and cby b, and are careful in our choice of the initial twin-freestring, these replacements will generate arbitrarily long twin-free strings. However, if we start with the twin-free stringaba, those substitutions immediately produce a string withtwins. They transform aba into abcacabc, which has twins.

If instead we start with the string a, those same substitu-tions repeated as often as we please will always produce

151

How the Other Half Thinks

twin-free strings. You could show this by reasoning much aswe did in the case of long twins.

The last word on strings formed of letters has yet to bestated. The work continues, guided by new questions in var-ious disciplines. For example, students of formal languages intheoretical computer science are examining strings that avoidpatterns other than twins. Mathematical biologists are mod-eling the cellular growth of organisms such as seaweed withthe aid of expansions in the spirit of those used in creatingtwin-free strings.

If, as it turned out, the history of the twin-free problemwas often unknown even to those working on it, imaginehow hard it is to predict its future and the future of relatedproblems.

152

Epilogue

A Backward Glance

Now that we have completed our journey let us see wherewe have traveled.In four of the chapters the strings are produced bychance: by throws of a needle (Chapter 1), by games playeduntil a team leads by two points (Chapter 2), by streaks andslumps (Chapter 4), and by counting ballots (Chapter 6).These chapters sample the theories of probability and statis-tics, which are concerned with questions such as, "Howmany people should we poll to get a reliable estimate of whatthe entire population thinks?"

In two of these chapters (Chapters 2 and 4) we add moreand more terms of an infinite collection of positive numbers.This illustrates the limit process of calculus. Calculus is thestudy of continuous change, such as the varying temperaturethroughout a lake or the trajectory of a rocket. Even the verydefinition of temperature requires calculus. Without calcu-lus, we would be back in the eighteenth century, without

153

Epilogue

trains, cars, planes, or electricity. Without electricity, therewould be no radio, television, or computers.

Chapter 3 on the complete triangle comes from topology,the study of space. Because the chapter is concerned with tri-angles and polygons, we might think it is part of Euclideangeometry. However, the lines joining the dots can be wigglycurves; they do not have to be straight lines in order for us tocarry out our counting of pebbles.

Near the end of that chapter we show that no matter howyou use a given set of dots to cut a polygon into triangles,you always get the same number of triangles. The reasoning,which involves adding up angles in two ways, makes use ofthe fact that the angles of a triangle add up to 180 degrees.The conclusion remains true even if the edges are wiggly. Inthis more general case the proof must resort to topologicalconcepts, for one no longer has the sum of the angles of a tri-angle as a tool.

Thrifty strings (Chapter 5) and Twins (Chapter 8) comefrom the field called combinatorics, the branch of mathemat-ics concerned with finite sets. Combinatorics plays a big rolein such varied applications as designing experiments, manag-ing airline schedules and reservations, and computer pro-gramming. It is one of the few areas of mathematics in whichan amateur can make a significant contribution.

Infinity (Chapter 7) is part of set theory, which providesthe foundation of all mathematics. In contrast to combina-torics, it is concerned primarily with infinite sets.

The eight chapters offer a glimpse into just a few of thehundreds of branches of mathematics thriving today. We livein a golden age of mathematics, both pure and applied, an agethat stretches back to the Renaissance without interruption.It shows every sign of going on indefinitely. Mathematicsremains vital, stimulated by old unsolved problems and by

154

A Backward Glance

new questions coming to it from such diverse sources asmolecular biology, chemistry, physics, computing, and math-ematics itself.

Mathematics can tempt all those who have preserved thespirit of the explorer.

155

This page intentionally left blank.

Appendixes

This page intentionally left blank.

APPENDIX A

Triangles

In Chapter 3 we used the fact that the sum of the threeI angles inside a triangle is 180 degrees—that is, it is a straightangle. The proof for this is short and elegant. After wepresent it, we generalize the theorem to polygons and applythe generalization to dissections of a polygon into triangles.A bit of background.

In the figure below four angles are labeled x, z, y, and t.We will use the same letters to denote the size of each angle,as measured in degrees. We will show that x is equal to y.

The two lines that look parallel actually are.

159

Appendix A

We have to start somewhere, and thus we will assumethat z equals t, an assumption that the picture suggests is cer-tainly plausible. Now x + z is equal to y + t since both anglesin each sum add up to a straight angle. Because z equals t, itfollows that x equals y.

Now consider a typical triangle, with angles A, B, and C,as shown here:

The dashed line is parallel to the side AC of the triangle. Wewill use this figure to show that A + B + C = 180 degrees.Observe that E equals A and that D equals C. Now,

B+ D+ E= 180 degrees

Replacing D with C and E with A in this equation shows thatB + C + A equals 180 degrees also.

Knowing the sum of the angles in any triangle, we caneasily find the sum of the angles in any polygonal circuit. Forexample, any quadrilateral can be cut into two triangles, asshown here:

160

Appendix A

Hence the sum of the angles in a four-sided polygon is 2times 180, or 360 degrees. Similar reasoning shows that thesum of the angles in a pentagon, or five-sided polygon, is 3times 180, or 540 degrees.

More generally, the sum of the angles in any polygon, is(the number of sides - 2) times 180 degrees. This total canalso be expressed as "(the number of corners - 2) times 180degrees." In a moment we will use this second form.

In Chapter 3, we showed that no matter how a given setof dots is used to cut a polygon into triangles, the number oftriangles will always be the same. Now we give an explicitformula for the number of those triangles. The angles in eachtriangle in a dissection contribute 180 degrees. Now countup the total of all the angles in terms of the dots, as we didbefore.

At each interior dot there are 360 degrees. At each doton the boundary that is not a corner, there are 180 degrees.

Triangles around Triangles around

inner dot border dot

The sum of the angles at the corners is (the number of cornerdots - 2) times 180 degrees. Therefore:

180 x number of triangles = (360 x number of interior dots)+ (180 x number of border dots that are not at corners)+ [180 x (number of corners - 2)]

I6I

Appendix A

Dividing both sides by 180 shows that

Number of triangles = (2 x number of interior dots)+ number of border dots + number of corners - 2

To put it more simply,

The number of triangles is 2 less than the total num-ber of dots plus the number of interior dots.

Once we choose the dots, this relation tells us how many tri-angles there will be, no matter how we choose to join thedots to form the triangles.

162

APPENDIX B

Twins: A Supplement

This appendix describes Thue's theorem and also myexperience using the computer to make twin-free strings.

Thue's Theorem

Thue took a very general approach by asking: What are someconditions on three words U, V, and W such that substitutingU for a, V for b, and W for c would replace any twin-freestring in a, b, and c by a (longer) twin-free string? As we sawin Chapter 8, U = abcab, V = acabcb, and W = acbcacb arethree such words.

He found that the following two conditions are enough.The first should not surprise us; that is, if it were not satis-fied, some twin-free strings of length 3 would be expanded tostrings with twins.

1. Each of the following 12 strings, when written interms of a, b, and c, is twin free: UVU, UVW, UWU,

163

Appendix B

UWV; VUV, VUW, VWU, VWV; WUV, WUW,

wvu, wvw.

2. None of the three words—U, V, or W—appears inany of the other two words.

Thue's proof is similar to Pleasants' for the case of longtwins.

If the three words have the same lengths, then condition2 is automatically satisfied. Therefore, to check that threewords of equal length expand twin-free strings to twin-freestrings, all we must do is check whether any of the 12 men-tioned strings is twin free.

The Computer and Twins

The approach used by Thue, Pleasants, and others didn'tcompletely satisfy my curiosity. I hoped that there would bea more direct construction, one that builds a twin-free stringone letter at a time. I decided to experiment to see if I coulddevise such a method.

I first tried several "automatic" approaches by hand. Ibegan by building up a string letter by letter, always choos-ing the letter, a, b, or c, that occurs earliest in the alphabet anddoes not introduce twins into the string I was forming. Thatmethod gives me a start of a. At the next step it gives b sincethe choice of a would produce the twins aa. The next stepprovides another a, and I reach the string aba. At the nextstep, a is forbidden because aa would form. Moreover, b isalso since it would produce the string abab, and twins again.So the next letter is c, and I reach abac. The next three stepsadd aba, and I have abacaba. Then the method runs into anobstacle. Both a and b clearly produce twins. But so does c,as you may check.

164

Appendix B

Always choosing the "earliest" gave me a twin-free stringof length 7. Next I decided to try a mix of "earliest" and "lat-est." By "latest" I mean "choose the letter that occurs latestin the alphabet and does not lead to twins." Of course, I wasstill restricted to the first three letters of the alphabet.

Letting E stand for earliest and L for latest, I tried ELL,a pattern I repeated until I got stuck.

Starting with E, earliest, I got an a. Then L, latest, gaveme c, and so I had ac. The next L gave me b since using cwould produce twins, cc. At that point I had obtained acb.Then I went on with ELL again. The next E gave me an a,and I had acba. L then produced acbac. The next L led to ana because both c and b introduced twins.

Continuing with this pattern yielded a string of length

26:

ELL ELL ELL ELL ELL ELL ELL ELL EL

acb aca bcb acb cac bac abc acb ac

Adding a to this string produces twins TT* with T of length8; adding b produces twins with T of length 3; adding c pro-duces cc.

I then tried other combinations of E's and L's using aprogram that the mathematician Dean Hickerson wrote forthe computer. With each attempt the program stopped. Thatraised a new question: Will every combination of E's and L's,when applied to three letters, always stop? I don't know, and,as is usual in mathematics, if you can't answer a question,you ask what you hope is an easier one.

Will every combination of E's and L's, repeatedly appliedto four letters, always stop?

Using Hickerson's program, which could apply to anynumber of letters, I experimented. Several combinations that

165

Appendix B

we tried stopped. However, the direction EEEEEEL, whichstands for "six earliest followed by one latest repeatedlyapplied" led to a very long string. When we shut down thecomputer after three solid days, the string had over 7 millionletters. We don't know whether the computation would everhave stopped.

It would require a book of some three thousand pages torecord the twin-free string the machine calculated. I wonderhow long it would have taken to produce that string letter byletter by hand, and then how long to check it.

To give some idea of the computer's speed, I should men-tion that the first thousand letters were produced in a splitsecond, almost as soon as my fingers left the keyboard.However, as the string lengthened, the computer sloweddown.

In any case I pose this very concrete question: Does theprogram with EEEEEEL (six E's and an L) ever stop whenapplied to four letters?

We might expect that a program that goes on for 7 mil-lion steps will go on forever, but that assumption may not bevalid. Consider what happened when I tried EEEEELLLL-LLL (five E's followed by seven L's). After it produced atwin-free string with 100,000 letters, I felt that the machinewould never stop. Indeed, it passed 200,000, then 300,000 let-ters. It was finally blocked when the string had grown to357,665 letters.

Clearly, the computer raises new questions but, fortu-nately, does not answer them.

166

For Further Reading

This page intentionally left blank.

The following books contain many chapters accessible to the layreader

R. Courant and H. Robbins, What Is Mathematics?, 2d ed.; rev. byI. Stewart. Oxford University Press, New York, 1941, reprinted.

T. Dantzig, Number, the Language of Science. 4th ed., Free Press(Simon and Schuster), New York, 1985.

K. Devlin, All the Math That's Fit to Print. Mathematical Associa-tion of America, Washington, D.C., 1994 (143 short articles,almost all published in the Manchester Guardian).

D. Gale, Tracking the Automatic Ant. Springer, New York, 1998(columns from Scientific American).

M. Gardner, Aha! Gotcha. W. H. Freeman, New York, 1982.

M. Gardner, Life and Other Mathematical Amusements. W. H. Free-man, New York, 1983.

M. Gardner, Penrose Tiles to Trapdoor Ciphers. W. H. Freeman,New York, 1989.

M. Gardner, Time Travel and Other Mathematical Bewilderments.W. H. Freeman, New York, 1987.

S. Golomb, Polyominoes, Princeton University Press, Princeton, 1994.

169

For Further Reading

S. K. Stein, Strength in Numbers. John Wiley & Sons, New York,1996.

S. K. Stein, Mathematics, the Man-Made Universe. Dover, Mine-ola, 1997.

S. K. Stein, Archimedes: What Did He Do Besides Cry Eureka?Mathematics Association of America, Washington, D.C., 1999.

The following technical references are either sources for some of thechapters or take some of the ideas further.

Chapter I The Needle and the Noodle

R. E. Miles and J. Serra, Geometrical Probability and BiologicalStudies, Lecture Notes in Biomathematics, 23d ed. Springer-Verlag, New York, 1978.

Chapter 2 Win by Two

T. Gilovich, R. Vallone, and A. Tversky, The Hot Hand in Basket-ball: On the Misperception of Random Sequences. CognitivePsychology, 17 (1985): 295-314.

S. K. Stein, Existence Out of Chaos. In R. Honsberger (ed.), Mathe-matical Plums, Mathematical Association of America, Washing-ton, D.C., 1979, pp. 62-93. (This has several examples of addinga collection of numbers in two ways to obtain information.)

Chapter 3 The Complete Triangle

These references illustrate some of the uses of Sperner's lemma.

R. Hochberg, C. McDiarmid, and M. Saks, On the Bandwidth of Tri-angulated Triangles, Discrete Mathematics, 138 (1995): 261-265.

E. A. Kasimatis, Dissections of Regular Polygons into Triangles ofEqual Areas, Discrete and Computational Geometry, 4 (1989):375-381.

P. Monsky, On Dividing a Square into Triangles, American Mathe-matical Monthly, 77 (1970): 160-164.

E. I. Sperner, Neuer Beweis fur die Invarianz der Dimensionzahlund des Gebietes, Abhandlungen aus dem MathematischenSeminar der Hamburgischen Universitat, 6 (1928): 265-272.

170

For Further Reading

E. I. Sperner, Fifty Years of Further Development of a Combinato-

rial Lemma, pts. A and B. In W. Forster (ed.), Numerical Solu-tions of Highly Nonlinear Problems. North HollandPublications Co., 1980, pp. 183-214.

S. K. Stein, A Generalized Conjecture about Cutting a Polygoninto Triangles of Equal Areas, Discrete Computational Geom-etry, 24 (2000): 141-145.

S. Stein and S. Szabo, Algebra and Tiling, Mathematics Associationof America, Washington, D.C., 1994, pp. 107-133.

F. E. Su, Rental Harmony: Sperner's Lemma in Fair Division,

American Mathematical Monthly, 106 (1999): 930-942.S. Wagon, Fourteen Proofs of a Result about Tiling a Rectangle,American Mathematical Monthly, 94 (1987): 601-617.

Chapter 5 Thrifty Strings

J. Burns and C. J. Mitchell, Coding Schemes for Two-DimensionalPosition Sensing. In M. J. Ganley (ed.), Cryptography andCoding 3, Clarendon Press, Oxford, 1993, pp. 31-66.

S. W. Golomb, Shift Register Sequences. Holden-Day, San Fran-cisco, 1967. (This describes how to produce thrifty strings alge-braically.)

Chapter 6 Counting Ballots

W. Feller, An Introduction to Probability Theory and Its Applica-tions, Vol. 1, John Wiley & Sons, New York, 1950, chap. 3.

Chapter 8 Twins

A. Lindenmayer, Mathematical Models for Cellular Interactions inDevelopment, Journal ofTheoretical Biology, 18 (1968): 280-315.

P. A. B. Pleasants, Non-repetitive Sequences, Proceedings of theCambridge Philosophical Society, 68 (1970): 267-274.

P. Prusinkiewicz and A. Lindenmayer, The Algorithmic Beauty ofPlants. Springer-Verlag, New York, 1990. (This contains manypictures of objects produced by algorithms that generalize theexpansion technique ofThue and Pleasants.)

G. Rozenbeerg and A. Salomaa (eds.), Lindenmayer Systems:Impacts on Theoretical Computer Science, Computer Graphics,and Developmental Biology. Springer-Verlag, New York, 1992.

171

This page intentionally left blank.

Subject Index

This page intentionally left blank.

A

Angle of reflection/incidence,121

Arshon, S. E., 138Average, 25

B

Ballot problem, 99-121description of, 99-101geometrical approach to,

107-118notation for, 102preliminary analysis of,

102-103proposed formula for,

104-107and reflections, 115-121Baseball Encyclopedia, 72BIST (built-in self-test), 95Brouwer's fixed-pointtheorem, 60

Buffon's problem, 1-19application of, 15-19experimenting with, 3^1,6-8

influence of length in,11-12

influence of shape in, 8-11needle problem, 1-4,

14-15noodle problem, 4-14Built-in self-test (BIST), 95

C

Calculus, 153

Code division multiple access

(CDMA), 95Combinatorics, 154Complete section, 46Complete triangle, 49-50Computers, 164-166Constructive proofs, 56

175

Index

Counting-two-ways

technique, 35-37, 46^7,51-52, 55-56, 58-59,161-162

Couplets, 76

D

Diagonal method, 131E

Endless series (see Infiniteseries)

Essay on Moral Arithmetic

(Georges Buffon), 1Existence proofs, 56Expansion, 139

F

Finite sets, 1235-tuplets, 764-tuplets, 76Full strings, 79

G

Gambling, 40-41Geometric probability, 15Graph theory, 87-95

H

Hiker-and-pail problem, 121"Hot hand" effect, 73

I

Infinite numbers, theory of,131

Infinite series, 32-37, 41-44, 73Infinite sets, 123-136George Cantor and,130-133, 136

Infinite sets (Cont.)definition of, 123-124finite sets vs., 123and Russell's paradox,

134-136size of, 126-129theory of, 130, 132-133

Intervals, 46

L

Length (of a word), 75Limit process, 153Los Angeles Dodgers, 65-70Losing streaks (see Slumps andstreaks)

N

Natural History, General andParticular (GeorgesBuffon), 1

Needle problem, Buffon, 1-4,14-15

New Math, 123

Noodle problem, Buffon, 4-14

w-tuplets, 76

P

Patterns, 13, 75Polygons, 5, 48Proofs, 56

Q

Quadruplets, 76Quintuplets, 76

R

Random walk, 39^0Reflection, 115-121Russell's paradox, 134-136

176

Index

S

Secret messages, 95-96Sequences, 32Series, 32

[text] Math

Viewer

Editor

Tools

[text] Math

Viewer

Editor