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 non-leap 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/highest-number.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/(N-1), 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:

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?

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.

The Pleasures of Problem Solving

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 maybe-if they are particularly devilish-even 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 joy-and the incomparable rewards-of strenuous thinking.

All-out 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 thirty-one dominoes, each of which can cover tow squares of the checkerboard. Can the dominoes be arranged so that they cover all sixty-two 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 thirty-one dominoes could not be made to cover the sixty-two 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 computer-programmers 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 hit-or-miss 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 thinkers-scientists, mathematicians, inventors, and so forth-have 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 reason-as you will later on in Chapter 6-to 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 self-assured 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 self-confidence 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 self-confidence. 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 elementary-school 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 two-pi 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 two-pi 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, since-you have my word for it-sound, 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 well-known 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 desk-top calculator-all 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 one-for 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 liar-and-truth-teller 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't-and 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 sixty-one 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.

Puzzles for next week

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 Course-18 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?