Notes from Week 1
You cannot think about thinking without thinking about thinking about something—Seymour Papert
We began with a recognition task  a set of numbers that should be
familiar:
3.14159  pi to five digits after the decimal  
365  number of days in a nonleap year 1 year = 365.242199 days 

1.618  PHI (the golden ratio) to three digits after the decimal 1/PHI is the golden ratio, which is created by the point C on line segment AB if AC/AB = CB/AC. This ratio has the numerical value 0.618... (The Golden Rule) 

18.7.21.69  www.mit.edu  
5280  number of feet in a mile  
2.54  number of centimeters in an inch  
364.4  number of Smoots (less one ear) across the bridge  
77  77 Mass. Ave.  
71.087/42.361  longitude/latitude of MIT  
E15  The Media Lab  
1 4 8 9 27  Retired numbers of the Boston Red Sox: 1 Bobby Doerr 4 Joe Cronin 8 Carl Yastremski 9 Ted Williams 27 Carlton FIsk 
I then asked everyone writing down a number on the back of a
card. I collected the cards, shuffled the deck, and then flipped the
cards over, revealing the number one at a time. I stopped when I got
to the (2nd) highest number in the deck. How did I (almost) do it?
See http://epigram.media.mit.edu/walter/highestnumber.html
We didn't go through this analysis in class, but I include it here for your amusement:
Can you do better than 1/N? How do you maximize your chances?
The odds of the first number being highest is 1/N. The odds one of the
second number being higher than the remaining numbers is 1/(N1), but the
odds of it being higher than the first number is 1/2. Continuing along
these lines, some patterns begin to emerge.
N=1
(a) 1 = 1/1
N=2
(a) 1/2 = 1/2
(b) (1/1) 1/2 = 1/2
N=3
(a) 1/3 = 2/6
(b) 1/1 (1/3) + 1/2 (1/3) = 2/6 + 1/6 = 3/6
(c) 2/2 (1/3) = 2/6
N=4
(a) 1/4 = 6/24
(b) 1/1 (1/4) + 1/2 (1/4) + 1/3 (1/4) = 6/24 + 3/24 + 2/24 = 11/24
(c) 2/2 (1/4) + 2/3 (1/4) = 6/24 + 4/24 = 10/24
(d) 3/3 (1/4) = 6/24
N=5
(a) 1/5 = 24/120
(b) 1/1 (1/5) + 1/2 (1/5) + 1/3 (1/5) + 1/4 (1/5) = 50/120
(c) 2/2 (1/5) + 2/3 (1/5) + 2/4 (1/5) = 52/120
(d) 3/3 (1/5) + 3/4 (1/5) = 42/120
(e) 4/4 (1/5) = 24/120
The coefficients form a pattern:
1/1  1/2  1/3  1/4  ...  1/(N1) 
2/2  2/3  2/4  ...  2/(N1)  
3/3  3/4  ...  3/(N1)  
4/4  ...  4/(N1)  
...  5/(N1)  
...  
(N1)/(N1) 
The harmonic series, 1/1+1/2+1/3+...+1/N diverges, but slowly. After 2.5*10^8 terms, the sum is still less than 20. (See http://mathworld.wolfram.com/HarmonicSeries.html for more about the harmonic.)
The optimal strategy, which does much better than 1/N, is to reveal some
numbers and then stop when you come to the next "highest" number. But how many
and what are the odds of winning?
N  i  odds 
1  0  1.0 
2  1  0.5 
3  1  0.5 
4  1  0.46 
5  2  0.43 
10  3  0.40 
15  5  0.39 
30  12  0.38 
As n increases, the best odds converge to 1/e at the N/e position.
Note: By Stirling's Formula, lim as N approaches infinity of ((N!)^(1/N))/N is 1/e.
Speaking of e: from Wolfram's Mathworld (http://mathworld.wolfram.com/e.html)
Examples of e mnemonics (Gardner 1959, 1991) include:
"By omnibus I traveled to Brooklyn" (6 digits).
"To disrupt a playroom is commonly a practice of children" (10 digits).
"It enables a numskull to memorize a quantity of numerals" (10 digits).
"I'm forming a mnemonic to remember a function in analysis" (10 digits).
"He repeats: I shouldn't be tippling, I shouldn't be toppling here!" (11
digits).
"In showing a painting to probably a critical or venomous lady, anger dominates.
O take guard, or she raves and shouts" (21 digits).
Here, the word "O" stands for the number 0.
A much more extensive mnemonic giving 40 digits is
"We present a mnemonic to memorize a constant so exciting that Euler exclaimed:
'!' when first it was found, yes, loudly '!'. My students perhaps will compute
e, use power or Taylor series, an easy summation formula, obvious, clear,
elegant!" (Barel 1995).
In the latter, 0s are represented with "!". A list of e mnemonics in
several languages is maintained by A. P. Hatzipolakis.
We then went through an informal description of problem solving comes from one of Jim Fixx's collections of puzzles.
from Solve It! by James F. Fixx
Fawcett Popular
Library, New York (1978)
(author of The Complete Book of
Running)
"I've got a problem!" What unpleasant thoughts those words bring to mind. Perhaps they recall the mental distress of some personal dilemma, of not being able to decide which way to turn or what to do next. Or perhaps they remind you of the frustration that makes you grind your teeth and chew the paint off your pencil as you grope for the solution to a tough question on a test in school.
Problems of that kind usually aren't a whole lot of fun. But there is another, different kind of problem that is fun, and that's the kind you'll find in this book. These are the problems that are deliberately calculated to stretch your mind, enlarge your understanding, strengthen your thought processes, and maybeif they are particularly devilisheven trick you into stumbling down a dead end in order to see whether you can find your way out of it. But whatever the main purpose of such problems, they always have another purpose, tool to amuse and delight you with sheer joyand the incomparable rewardsof strenuous thinking.
Allout thinking brings two distinct kinds of fun.
First, there is the delight that comes simply from working on a problem, the fun of the thinking process itself. It can be the result of many things: of arriving at a solution so swiftly and so purposefully that you astonish yourself; of surmounting the confusion and helplessness you feel when you are momentarily convinced that a problem can't possibly be solved; or perhaps of thinking your to sudden insight that transforms a maddening complication into something so simple that you laugh out loud when you hit upon it.
Second, there is what has been described as "the thrill of success." Solving a tough problem can be just as rewarding as hitting a home run or sinking a difficult basketball shot. Scientists and inventors have written of the sense of excitement that comes as they suddenly find the solution to a problem that has been on their minds for a long time. This excitement, they report, is one of life's highest pleasures.
A homely illustration will show what I mean.
A few years ago a friend gave me a seemingly simple problem. You have a checkerboard, he said, from which two diagonally opposite corners have been removed. You also have thirtyone dominoes, each of which can cover tow squares of the checkerboard. Can the dominoes be arranged so that they cover all sixtytwo squares of the checkerboard? If so, how? If not, why not?
I'll bet it sounds easy to you. It did to me, too. Confidently, I got out a checkerboard and a set of dominoes. Placing the dominoes this way and then that, I tried for some time to cover all of the squares. No matter how hard I tried, however, I was unable to. Something always went wrong and I would wind up with isolated leftover squares. Before long I was at the edge of hopeless frustration.
Suddenly it occurred to me to try something different. What would happen, I wondered, if I wore to use an altogether different tack? What if I assumed that the thirtyone dominoes could not be made to cover the sixtytwo squares and set out to prove that? Thinking about it this way brought quite different results. It was, in fact, only a matter of minutes before I saw that 1) two diagonally opposite squares are always the same color, that 2) a domino must always cover two squares of different colors, and that 3) the problem therefore could not be solved because there would always be too few squares of one color or the other. The solution was so neat, so brief, and so elegant that it still gives me pleasure whenever I think of it.
Learning to solve problems like the ones in this book will give you bonuses beyond mere pleasure. Among other benefits, they will help you in your schoolwork, and later on, in whatever kind of work you decide to do. When, for example, two thousand computerprogrammers were asked to list their hobbies, it was found that those who spent time doing puzzles and playing logic games were the best at their jobs. A senior instructor at a government computer school in Washington D.C., told me, "You can hardly visit a computer center without being challenged to solve a puzzle."
If, then, puzzles not only bring us pleasure, but also help us to work and learn more effectively, is it not worthwhile to learn to do them well? It certainly is. Fortunately, there are several ways to reach that goal.
Problem solving is not just a hitormiss process. There are four distinct stages. Moshe F. Rubinstein, a specialist in scientific problem solving at the University of California, describes them as follows:
Stage 1: Preparation. You go over the elements of the problem and
study their relationships.
Stage 2: Incubation. Unless you've
been able to solve the problem quickly, you sleep on it. You may be
frustrated at this stage because you haven't been able to find an
answer and don't see how you're possibly going to.
Stage 3:
Inspiration. You feel a spark of excitement as a solution (or a
possible path to one) suddenly appears.
Stage 4:
Verification. You check the solution to see if it really works.
These four steps are exactly the ones many of the world's most gifted thinkersscientists, mathematicians, inventors, and so forthhave followed in making some of history's significant discoveries. Merely to know what the steps are, however, is not necessarily the same as being able to follow them. To do that, we need a more detailed set of rules.
Such a set of rules follows. Actually, they are not so much rules as guidelines, for when it comes to thinking, there are very few unbreakable rules. If you keep these guidelines in mind, they will help you solve many problems, even difficult ones. Since you will be using them again and again, they are worth memorizing. For convenience, we can call them the "Scaredycat" technique because each rule begins with a successive letter of that word.
Here, step by step, are the ten rules of the Scaredycat technique, with a few explanatory comments about each:
Rule 1: Study the question carefully. Read the problem over, several times if you like, to be sure you understand exactly what is being asked. This is always an important rule, but it is particularly crucial if a question is complicated of if you have reasonas you will later on in Chapter 6to suspect that an attempt is being made to trick you. Consider, for example, the following question:
If an airplane crashes directly on the boundary between California and Oregon, where are the survivors buried?
If you are not alert to exactly what you are being asked, it may be quite some time before you abandon the apparent question and realize (with appropriate embarrassment) that we don't customarily bury people alive.
Rule 2: Confidently start work. In solving puzzles, a selfassured attitude is half the battle. When the confident person is momentarily stumped, he is not discouraged but presses ahead, certain that sooner or later a solution will come. Before you begin, it will help your selfconfidence if you have everything you're likely to need: pencils, paper, a ruler, scissors, and perhaps a dictionary to make sure you know the exact meaning of all of the words in a problem. (If you mistake "radius" for "diameter," you're in trouble.) As you work, do so with purpose and energy. If one effort fails, move on to another. Above all, don't say, "That one's too tough for me!" Chances are it only looks too tough and is readily solvable once you discover the key. As your list of successfully solved problems grows, so will your selfconfidence. By the time you've been through all of the problems in this book, you'll be virtually unstoppable.
Rule 3: Appraise the context. If you look closely, you can often gather important clues from the problem's surroundings. Consider, for example, this one, adapted from a puzzle in one of my earlier books:
Two bicycles are approaching each other at a constant speed of ten miles an hour. When they are two miles apart, a bird leaves one bicycle and flies toward the other at a speed of fifty miles an hour. Upon reaching that bicycle it immediately reverses direction. This continues until the two bicycles meet. How far does the bird fly altogether?
At first glance, it appears that the only way to solve this problem is to add up the progressively smaller distances that the bird covers as the two bicycles approach each other. But that, an alert and thoughtful reader of my book would realize, was a considerably tougher problem than I was likely to include, especially since I myself am shaky with anything more complicated than elementaryschool mathematics. It was a safe guess, therefore, that there had to be an easier way to solve the problem. And, sure enough, there was: Simply figure out how long it is before the two bicycles reach each other (six minutes) and calculate how much distances the bird covers in that time (five miles).
[The story goes that Von Neumann did the infinite
series in his head, but this is a matter historical debate. Another
cute, but exasperating Von Neumann story I found on the Web:
From: thommark@access5.digex.net (Mark A. Thomas)
How about the apocryphal story about the MIT student who cornered
the famous John von Neumann in the hallway:
Student: "Er, excuse me, Professor von Neumann, could you please
help me with a calculus problem?"
John: "Okay, sonny, if it's real quick  I'm a busy man."
Student: "I'm having trouble with this integral".
John: "Let's have a look." (insert brief pause here)
"Alright, sonny, the answer's twopi over 5."
Student: "I know that, sir, the answer's in the back  I'm
having trouble deriving it, though."
John: "Okay, let me see it again." (another pause)
"The answer's twopi over 5."
Student (frustrated): "Uh, sir, I _know_ the answer, I just don't
see how to derive it."
John: "Whaddya want, sonny, I worked the problem in two
different ways!"
WB]
Much the same reasoning can be applied to many of the problems in this book, sinceyou have my word for itsound, logical thinking is far more important than advanced mathematical ability. (In fact, as you will see in the discussion of Rule 6 below, too much mathematical sophistication may hurt rather than help.
Rule 4: Relax. Sometimes intuition and imagination are more reliable allies than straightforward effort. A friend who is an excellent puzzle solver once referred to a "sideways style" of thinking—that is, one that approaches a problem from an unexpected direction. The sideways style comes most easily when we are relaxed and don't press too hard. Relaxing is a particularly useful strategy when you feel frustrated by your inability to find a solution. There is an odd paradox in puzzle solving; trying too hard and caring too much are more likely to slow you down than speed you up. If, for a moment, you pretend that you don't really care, an answer may simply pop into your head.
Rule 5: Expect to wait. Not all problems, and certainly not all of those in this book, can be solved by hard work alone. Many depend upon a sudden insight or inspiration. But insight is a curious and sometimes perverse thing; it doesn't always arrive when you need it most. André Marie Ampère, whose surname we have given to a unit of electrical current, once tried repeatedly to find the solution to a mathematical problem. Over a period of several days, he returned to it again and again. Ampère describes how a solution finally came to him: "I had sought twenty times unsuccessfully for this solution. For some days I had carried the idea about with me continually. At last, I do not know how, I found it." This is the incubation period mentioned earlier. Where some problems are concerned, waiting is an inescapable part of the solution.
Rule 6: Don't accept unnecessary limitations. In a wellknown problem you are asked to connect nine dots with four straight, connected lines. Most people, when first confronted with this problem, are baffled. They make one attempt after another, but with no success. The reason for their difficulty is simple: They assume that they are not permitted to go outside the imaginary boundary created by the outer dots. Actually, of course, no such limitation has been expressed. As soon as you see that, the solution comes easily.
[A nasty variant of thinking outside the box
Connect the dots using just three
connected line segments.
Note that I was careful to
say "dots", not "points." WB]
Sometimes, as mentioned, too much mathematical knowledge can create its own limitations. You are, of course, familiar with the idea of a series. If I were to ask you to give the next number in this list:
3, 6, 9, 12, 15, ___
you would have little difficulty in saying "18," since it is easy to see that each number is simply its predecessor plus three.
Not long ago in New York City I asked a friend who has had considerable mathematical training to tell me the next number in this series:
4, 14, 23, 34, 42, ___
He pondered, scribbled, wore a couple of pencils down to stubs, and finally got out his desktop calculatorall to no avail. Finally, after he had shamefacedly given up, I pointed out that the numbers were those of the subway stops on the very line he rides to and from work every day! His mathematical expertise had made him look for a complicated answer rather than a simple one.
[The Independent Subway (IND) was formed by the City in the 1920s as an "independent" system that was not connected to the IRT or BMT lines. When no private operator could be found, the City's Board of Transportation began operation itself. This system consisted of entirely subway construction with only one elevated portion, a short section over the Gowanus Canal in Brooklyn. The IND lines were the 8th Avenue and 6th Avenue trunk lines in Manhattan, the Queens Boulevard subway in Queens, the Concourse subway in the Bronx, the Fulton Street subway in Brooklyn, the Brooklyn/Queens Crosstown, and the line in Brooklyn via Smith/9th Streets to Church Avenue. Certain IND lines underpinned existing IRT and BMT elevated lines (6th Avenue and Fulton Street). The IND is today's A, C, E, B, D, F, Q, and G. From www.nycvisit.com WB]
Rule 7: Yesterday's problems may help. Problems are very much like brothers and sisters. In some ways they may be very different from each other, but there are usually family resemblances. This is why, when you first encounter a problem, it's wise to ask yourself whether it's like any other problems you've seen. If, for example, you browse through books of puzzles in the library, you will invariably find problems in which some people always lie while others always tell the truth. Here is a typical example:
A traveler comes to a fork in a road and doesn't know which way to go to reach his destination. There are two people at the fork, one of whom always lies while the other always tells the truth. The traveler doesn't know which is which. He is permitted to ask only one of the people one question to find his way. What is his question and which one does he ask?
Once you realize that the solution lies in asking two questions in onefor example, "If I were to ask you which road leads to Los Altos, which one would you say?"the answer comes easily. And so do the answers to most other liarandtruthteller questions, since almost all of them (thought not, just to make matters interesting, the two that appear later in this book) rely on exactly the same principle.
Rule 8: Change the problem. At the beginning of this chapter we looked at the problem of the checkerboard with two missing squares. You'll remember that when I was unable to prove that the dominoes could cover all of the squares, I decided to try proving that they couldn'tand the answer came immediately. Changing a problem in that way is a valuable technique whenever you can use it. Sometimes, of course, you can't. In those cases, you simply have to push ahead in your original direction.
Rule 9: Ask questions. Although you will probably be working alone most of the time, there's no law that you must always solve problems without help. Sometimes, in fact, part of the fun comes from comparing ideas with others. Even if a friend or classmate can't actually solve a problem for, he or she may point the way to a missing clue. You'll get the most satisfaction, of course, from solving a problem by yourself, but it's far better to use help than not to find a solution at all.
Rule 10: Time brings all things. Often we fail to solve problems because we aren't persistent enough. We give up before we've really begun. Many times you don't begin to understand a problem's real nature until you have become convinced that it can't be solved at all. This happened to me not long ago when someone handed me this problem:
Two people were talking. One said to the other, "I have three
sons whose ages I want you to ascertain from the following clues:
a. The sum of their ages is thirteen.
b. The product of their
ages is the same as your age.
c. My oldest son weighs sixtyone
pounds."
"Stop," said the second person. "I
know their ages."
What are they?
For a long time I couldn't get anywhere with that problem. What, I wondered could the weight of the oldest son possibly have to do with anything? It wasn't until I had struggled for a long time that it occurred to me that the weight itself probably didn't matter at all and that the third clue might be telling me something entirely different. I was, of course, right. There is no substitute for patience and persistence.
[An alternative version goes as follows:
Two men meet on the
street. They haven't seen each other for many years. They talk about
various things, and then after some time one of them says: "Since
you're a professor in mathematics, I'd like to give you a problem to
solve. You know, today's a very special day for me. All three of my
sons celebrate their birthday this very day! So, can you tell me how
old each of them is?"
"Sure," answers the
mathematician, "but you'll have to tell me something about
them."
"OK, I'll give you some hints," replies
the father of the three sons, "The product of the ages of my sons
is 36."
"That's fine," says the mathematician,
"but I'll need more than just this."
"The sum of
their ages is equal to the number of windows in that building,"
says the father pointing at a structure next to them. The
mathematician thinks for some time and replies, "Still I need an
additional hint to solve your puzzle."
"My oldest son
has blue eyes," says the other man.
"Oh, this is
sufficient!" exclaims the mathematician, and he gives the father
the correct answer: the ages of his three sons.–from How to
Solve It: Modern Heuristics by Michalewicz and Fogel WB]
These, then are ten rules that will serve you well in problem solving. They are not, needless to say, guaranteed to solve all problems, but they will greatly increase the likelihood of your finding a solution—and the likelihood, too, that you will experience what I referred to earlier as the thrill of success.
They are, in short, rules for getting more fun out of thinking. And that, I hope you'll agree, is what thinking, at its most rewarding, is really all about.
We are given that X and Y are two integers; both X and Y are
greater than 1, X does not equal Y; and X+Y is less than 100. Foo and
Bar are two talented Course18 undergrads. Foo is given the sum, and
Bar is given the product of these numbers:
Bar says, "I
cannot find the numbers."
Foo says, "I was sure that
you could not find them."
Bar says, "Then, I found the
numbers."
Foo says, "If you could find them, then I
also found them."
What are the numbers?
Sacrafice flies
On June 24, 2005, Pedro Martinez and the New York Mets beat the hated New York Yankees. In that game, the Mets set a Major League record by hitting three sacrafice flies in one inning. How were they able to do this?