How To Solve It

If I could require every American schoolchild of normal intelligence to read one book, it would be George Pólya’s How To Solve It. (Second choice is Henry Hazlitt’s Economics in One Lesson. I keep extra copies of both books on hand to give away as necessary.) Pólya was born in Hungary and taught mathematics at several European universities before ending up at Stanford. Like the authors of all the best pedagogical texts, he was a superb practitioner. Pólya made important original contributions in probability theory, combinatorics, complex analysis, and other fields. He published How To Solve It in 1945; it has since sold more than a million copies. He died in 1985 at an immense age.

How To Solve It, among its other virtues, is a model of English prose style; I will let Pólya himself describe what he’s up to:

The author remembers the time when he was a student himself, a somewhat ambitious student, eager to understand a little mathematics and physics. He listened to lectures, read books, tried to take in the solutions and the facts presented, but there was a question that disturbed him again and again: “Yes, the solution seems to work, it appears to be correct; but how is it possible to invent such a solution? Yes, this experiment seems to work, this appears to be a fact; but how can people discover such facts? And how could I invent or discover such things by myself?” Today the author is teaching mathematics at a university; he thinks or hopes that some of his more eager students ask similar questions and he tries to satisfy their curiosity.

Math students are regularly exhorted to “show your work,” while the great mathematicians hide theirs. Euclid’s proof that the angles of a triangle sum to 180 degrees is a masterpiece of logical thought, but however he arrived at it, it was assuredly not by the route shown in the Elements. The proofs came first, the axioms after. One can admire but not emulate. In short, what math education lacks is heuristic, and this is what Pólya endeavors to supply.

The way to write about Pólya is to solve problems with his techniques. Abbas Raza at 3 Quarks Daily provided an occasion by posting fourteen moderately difficult logic problems, none requiring mathematical background. I’ve rearranged them slightly. Most of the problems are famous; you have probably seen some of them before. You may want to have at the problems first before you read my solutions and commentary on how I used Pólya’s techniques to find them.

1. You are given two ropes and a lighter. This is the only equipment you can use. You are told that each of the two ropes has the following property: if you light one end of the rope, it will take exactly one hour to burn all the way to the other end. But it doesn’t have to burn at a uniform rate. In other words, half the rope may burn in the first five minutes, and then the other half would take 55 minutes. The rate at which the two ropes burn is not necessarily the same, so the second rope will also take an hour to burn from one end to the other, but may do it at some varying rate, which is not necessarily the same as the one for the first rope. Now you are asked to measure a period of 45 minutes. How will you do it?

Solution: Light the first rope at both ends, and the second at one end. When the first rope has completely burned, 30 minutes have elasped. Now light the other end of the second rope. When the second rope has completely burned, 45 minutes have elapsed.

Commentary: “If you can’t solve a problem,” Pólya says, “there is an easier problem you can solve: find it.” Measuring 45 minutes may seem impossible at first, but how about 30 minutes? Thinking about 30 minutes instead, you may hit on the bright idea of lighting the rope at both ends. From there you need one more bright idea: that you need not light both ends simultaneously. Most people, including me, arrive at the second idea very quickly after thinking of the first; but I once saw an excellent problem solver find the first idea immediately and take quite a while to find the second.

2. You have 50 quarters on the table in front of you. You are blindfolded and cannot discern whether a coin is heads up or tails up by feeling it. You are told that x coins are heads up, where 0 < = x

Solution: You are given x, the number of heads. Create a subgroup of x coins. Flip them all.

Commentary: Pólya asks: Did you use the whole condition? The condition here is more liberal than it looks. You need not know the number of heads in each pile. Neither must the two piles contain the same number of coins, provided the number of heads in the two piles is the same.

Pólya also asks: Did you use all the data? Here we are given the total number of coins, which is doubtfully relevant, except that it is large enough to make the problem difficult. More important, we are given x, the number of coins heads up. The solution is very likely to involve flipping x coins. In fact it is a simple matter of doing just that.

Pólya finally asks: Can you check the solution? Introducing suitable notation, another Pólya suggestion, yields a satisfying way to do so. x is the number of coins that are heads up; 50 – x, then, is the number of coins tails up. We divide the coins into two groups, of x and 50 – x coins. Let y be the number of heads in the x group. Then the number of heads in the 50 – x group is x – y. Now we flip all the coins in the x group. The number of heads becomes x – y. The two groups contain the same number of heads. This also demonstrates, as we suspected, that 50 is indeed irrelevant; the solution works no matter how many coins you begin with.

3. A farmer is returning from town with a dog, a chicken and some corn. He arrives at a river that he must cross, but all that is available to him is a small raft large enough to hold him and one of his three possessions. He may not leave the dog alone with the chicken, for the dog will eat it. Furthermore, he may not leave the chicken alone with the corn, for the chicken will eat it. How can he bring everything across the river safely?

Solution: Bring the chicken across. Return alone and bring the dog across. Return with the chicken, and bring the corn across. Return alone and bring the chicken across.

Commentary: This is a “hill-climbing” problem; you proceed by steps until you reach the goal. It can be difficult to solve because in hill-climbing it is natural to try to proceed directly, which gets you stuck at a local optimum of two items across the river.

Pólya says, translating the Greek mathematician Pappus of Alexandria (circa 300 AD), “start from what is required and assume what is sought as already found.” Next “inquire from what antecedent the desired result could be derived.” Beginning at the end, we can see that on the farmer’s last raft trip he must bring the chicken across, because only the dog and corn can be left together safely. But for the same reason he must also bring the chicken across on his first trip. Putting this to yourself explicitly, you may eventually realize that the chicken must go back and forth and the solution will immediately present itself.

4. Late one evening, four hikers find themselves at a rope bridge spanning a wide river. The bridge is not very secure and can hold only two people at a time. Since it is quite dark, a flashlight is needed to cross the bridge and only one hiker had brought his. One of the hikers can cross the bridge in one minute, another in two minutes, another in five minutes and the fourth in ten minutes. When two people cross, they can only walk as fast as the slower of the two hikers. How can they all cross the bridge in 17 minutes? No, they cannot throw the flashlight across the river.

Solution: Two and One cross (2 minutes). One returns (3 minutes). Ten and Five cross (13 minutes). Two returns (15 minutes). Two and One cross (17 minutes).

Commentary: Pólya asks: If you had a solution, what would it look like? Certainly we know that Ten and Five cannot cross more than once, or we are immediately at 20 minutes plus. But if Ten and Five cross separately we are still over 17 minutes, since there must be three other trips of at least a minute each. Therefore Ten and Five must cross together. This cannot happen at the beginning — otherwise one would have have to return — or at the end — since someone would have to return with the flashlight and would remain. Therefore they must cross in the middle. The solution appears.

Pólya also asks: Do you know a related problem? This problem bears an interesting reciprocal relationship to Problem 3, of the dog, chicken, and corn. There we infer the procedure from the first and last trips; here we infer it from the trip in the middle.

5. You have four chains. Each chain has three links in it. Although it is difficult to cut the links, you wish to make a loop with all 12 links. What is the smallest number of cuts you must make to accomplish this task?

Solution: Three cuts. You cut all three links of a single chain and use them to connect the other three together.

Commentary: Cutting one link in each of the four chains will obviously do the job, but that’s not interesting enough to be the right answer. Can we do better?

Pólya suggests enumerating the solution space, when possible; or guessing, to put it bluntly. How many different ways can we cut three links? Well, we can cut one from each of three chains: that won’t work. We can cut two from one chain: that doesn’t help either. Or we can cut all three from a single chain… aha!

6. Before you lie three closed boxes. They are labeled Blue Jellybeans, Red Jellybeans and Blue & Red Jellybeans. In fact, all the boxes are filled with jellybeans. One with just blue, one with just red and one with both blue and red. However, all the boxes are incorrectly labeled. You may reach into one box and pull out only one jellybean. Which box should you select from to correctly label the boxes?

Solution: Choose from the box labeled Blue & Red.

Commentary: Another good guessing problem. The solution is obvious. It is functionally equivalent to choose from the Blue or Red box, and the problem stipulates a single answer, which must be Blue and Red.

All that is left is the reasoning. Suppose you choose a red jellybean. Then you know the Blue & Red box should be labeled Red, and that, since the other two boxes are also mislabeled, that the Red box must be Blue and the Blue box must be Blue and Red.

Guess first, reason later: it works more often than you’d think.

7. Walking down the street one day, I met a woman strolling with her daughter. “What a lovely child,” I remarked. “In fact, I have two children,” she replied. What is the probability that both of her children are girls?

Solution: There are four prior possibilities for the sex distribution of her two children: boy-boy, girl-girl, boy-girl, and girl-boy. We’ve seen a girl, so boy-boy is out. Of the three remaining possibilities, once you’ve revealed a girl, a boy remains in two of them. Therefore the probability that the other child is a girl, P(G) = 1/3.

Commentary: The difficulty here is less in finding the answer than in believing it. As with the Monty Hall Problem, many people deny that the solution is true, and they have distinguished company. (The solution depends subtly on the precise wording with which the problem is given; this comment thread has an extensive discussion, which is beyond the scope of this discussion.)

Pólya asks: Can you draw a diagram? No, but you can model the problem experimentally. Dump a bunch of coins on the table and pair them up randomly. Remove all the tail/tail pairs. Now tabulate the results for the rest of the pairs. They will be tail/head approximately 2/3 of the time.

8. A glass of water with a single ice cube sits on a table. When the ice has completely melted, will the level of the water have increased, decreased or remain unchanged?

Solution: The water level sinks, because ice has lower specific gravity than water.

Commentary: Pólya asks: Have you seen this problem before? You have. It’s the famous problem Archimedes solved in his bath. A king asked Archimedes to determine if a crown he owned was pure gold, without melting it down. Archimedes stepped into his bath, watched the water rise, and ran naked into the street, shouting “Eureka!” Maybe not. At any rate, he realized that his body displaced an equivalent volume of water, and he could measure the volume of any irregular object the same way, by submerging it.

Once Archimedes determined the volume of the crown, he simply weighed it against a lump of gold of identical volume. Gold is denser than silver, so if the crown was lighter, it had been adulterated. Water is denser than ice, so the water level sinks as the ice melts.

Abbas Raza, after setting this problem, got it wrong. The floating cube does not “displace its own weight in water”; it displaces its own volume in water. Had he regarded Pólya’s advice to check the solution, by melting a few ice cubes in a glass of water, he would have spared himself some embarrassment. (See the update for who’s embarrassed now.)

9. You are given eight coins and told that one of them is counterfeit. The counterfeit one is slightly heavier than the other seven. Otherwise, the coins look identical. Using a simple balance scale, can you determine which coin is counterfeit using the scale only twice?

Solution: Weigh three against three. If they are equal then the counterfeit is one of two coins and it’s easy. If not, then the counterfeit is one of three coins. Take two of the three and weigh them against each other. Whichever is heavier is the counterfeit, or, if they’re equal, the third is counterfeit.

Commentary: This problem would be far easier if it were given with nine coins instead of eight. The same solution applies, but since three divides nine evenly, and two does not, you would immediately think to weigh three against three. With eight coins the opposite is true. You think of weighing four against four, and it may be some time before you disentangle yourself.

10. There are two gallon containers. One is filled with water and the other is filled with wine. Three ounces of the wine are poured into the water container. Then, three ounces from the water container are poured into the wine. Now that each container has a gallon of liquid, which is greater: the amount of water in the wine container or the amount of wine in the water container?

Solution: The water in the wine is equal to the wine in the water.

Commentary: This problem, like Problem 2, is overspecified. In fact almost all of the given data — how much liquid is in each container, the mixing sequence — is irrelevant. It matters only that the two containers begin and end with equal amounts of liquid. Pólya asks: Did you use all the data? Here that question gets you into trouble.

But Pólya also says that sometimes the general problem is easier to solve. (In computer science the general problem is always easier to solve.) He has caught grief for this remark, and the example he gives is somewhat artificial, but here it bears out. The specifics make the problem confusing.

Of course if you solve the general problem then you have, by definition, not used all the data. Sometimes one procedure works; sometimes its opposite.

11. Other than the North Pole, where on this planet is it possible to walk one mile due south, one mile due east and one mile due north and end up exactly where you began?

Solution: Pólya gives this exact problem in How To Solve It in its more famous form, in which a bear does the walking and the problem is what color is the bear. I will quote his solution, if only to demonstrate how comprehensive his thinking is next to mine:

You think that the bear was white and the point P is the North Pole? Can you prove that this is correct? As it was more or less understood, we idealize the question. We regard the globe as exactly spherical and the bear as a moving material point. This point, moving due south or due north, describes an arc of a meridian and it describes an arc of a parallel circle (parallel to the equator) when it moves due east. We have to distinguish two cases.

1. If the bear returns to the point P along a meridian different from the one along which he left P, P is necessarily the North Pole. In fact the only other point of the globe in which two meridians meet is the South Pole, but the bear could leave this pole only in moving northward.

2. The bear could return to the point P along the same meridian he left P if, when walking one mile due east, he describes a parallel circle exactly n times, where n may be 1, 2, 3… In this case P is not the North Pole, but a point on a parallel circle very close to the South Pole (the perimeter of which, expressed in miles, is slightly inferior to 2Ï€ + 1/n).

Commentary: Before solving the problem Pólya offers the following hints:

What is the unknown? The color of a bear — but how could we find the color of a bear from mathematical data? What is given? A geometrical situation — but it seems self-contradictory: how could the bear, after walking three miles in the manner described, return to his starting point?

12. I was visiting a friend one evening and remembered that he had three daughters. I asked him how old they were. “The product of their ages is 72,” he answered. I asked, “Is there anything else you can tell me?” “Yes,” he replied, “the sum of their ages is equal to the number of my house.” I stepped outside to see what the house number was. Upon returning inside, I said to my host, “I’m sorry, but I still can’t figure out their ages.” He responded apologetically, “I’m sorry. I forgot to mention that my oldest daughter likes strawberry shortcake.” With this information, I was able to determine all of their ages. How old is each daughter?

Solution: The factors of 72 can be combined into three factors with identical sums only one way: 6, 6, and 2; and 3, 3, and 8, both of which sum to 14. “My oldest daughter likes strawberry shortcake” implies that there is one daughter who is older than the other two. (This isn’t quite sound, since two of the daughters could be, say, 6 and 1 month and 6 and 11 months, and even twins are not precisely the same age; but, as Pólya would put it, we idealize the question, as it is more or less understood.) Therefore 3, 3, and 8 are the ages.

Commentary: Pólya might suggest introducing suitable notation. Let the ages of the three daughters be x, y, z. There must be a uniqely oldest daughter, so x > y >=z. Let S be the sum of their ages.

We have:

x * y * z = 72

x + y + z = S

Now we enumerate x, y, and z, looking for those with non-unique sums. Since the prime factors of 72 are (2^3) * (3^2), the job is pretty simple. The solution suggests itself shortly.

13. The surface of a distant planet is covered with water except for one small island on the planet’s equator. On this island is an airport with a fleet of identical planes. One pilot has a mission to fly around the planet along its equator and return to the island. The problem is that each plane only has enough fuel to fly a plane half way around the planet. Fortunately, each plane can be refueled by any other plane midair. Assuming that refuelings can happen instantaneously and all the planes fly at the same speed, what is the smallest number of planes needed for this mission?

Solution: Three planes. Send out all three, flying clockwise. At 45 degrees each plane has burned a quarter of its fuel. Plane 1 gives a quarter of its remaining fuel each to Plane 2 and Plane 3 and uses its remaining quarter-tank to return to base. Planes 2 and 3, now both full, continue to 90 degrees. Plane 2 gives Plane 3 one-half of its fuel and uses its remaining half-tank to return to base. Plane 3 continues to 270 degrees. When it reaches 180 degrees, Planes 1 and 2, having refueled at base (Plane 2 will have just returned by then), fly out counter-clockwise, using the same procedure.

Commentary: Pólya says, first be sure you understand the problem. Abbas Raza specified, in reply to a reader’s query, that the planes may not fly suicide missions. Oddly, if they were permitted to, the answer would still be three, although two of them would plunge into the drink. But then the problem would not be interesting.

14. You find yourself in a room with three light switches. In a room upstairs stands a single lamp with a single light bulb on a table. One of the switches controls that lamp, whereas the other two switches do nothing at all. It is your task to determine which of the three switches controls the light upstairs. The catch: once you go upstairs to the room with the lamp, you may not return to the room with the switches. There is no way to see if the lamp is lit without entering the room upstairs. How do you do it?

Solution: You turn one on. You turn a second one on, wait a minute, then turn it off. Then you go upstairs and see if the bulb is off, on, or warm.

Commentary: Here the question that is so effective for Problem 12 — could you restate the problem? — can lead you astray. Introducing notation will probably also steer you wrong. The solution depends on the physical characteristics of the problem elements, and different, more abstract language may cause you to miss it. (This is why many mathematicians hate this problem.) But that’s why it’s called heuristic, as Pólya explains:

You should ask no question, make no suggestion, indiscriminately, following some rigid habit. Be prepared for various questions and suggestions and use your judgment. You are doing a hard and exciting problem; the step you are going to try next should be prompted by an attentive and open-minded consideration of the problem before you….

And if you are inclined to be a pedant and must rely on some rule learn this one: Always use your own brains first.

Update: On Problem 8, as Adam points out in the comments, Abbas Raza is right and I am wrong. The best correct explanation is here. Pólya does not say, but should, that if you insist on solving problems in public you do so at your peril. I will leave up my own foolishness as a lesson in hubris.