Notes on Problem Solving II
Math 3250/5250 - Problem Solving and Computing
Fall 2000
We should start with one basic truth: There are no universal, infallible procedures for mathematical problem solving. If there were, there would be no unsolved problems. And because there are not, problem solving is always fresh and challenging. Having said that, it is still worthwhile to try and identify some procedures and patterns that recur frequently in problem solving. These notes explore three different patterns in problem solving: In each case, several examples that involve these patterns are posed. Try to work each example. Only as a last resort should you look at the solutions are given at the end of the notes! As you work these examples and the exercises that follow, try to ``watch'' yourself work and identify the sorts of insights and tools you use.

1. Insight is Helpful The following problems have a direct, and often tedious solution. But some ingenuity can often reduce the amount of computation and lead to a simpler solution .

Example: An Old Classic: The Chelsea Pensioners. If 70% of the pensioners have lost an eye, 75% have lost an ear, 80% have lost an arm and 85% have lost a leg, what percentage of the pensioners (at least) have lost an eye, an ear, an arm and a leg ?

Example: The Second Race. Jill and Jack ran a 100 meter race. When Jill crossed the finish line Jack had run only 95 meters. They decided to race again and Jill handicapped herself by starting 5 meters behind the starting line. If they both run at the same constant speed as they did in the first race, who wins the second race ?

Example: The Maze. Consider the square maze shown in the figure below. The outside dimensions are 100 meters by 100 meters. The walls have a negligible thickness and the path is everywhere 2 meters wide. How far would you walk from the entrance (marked with a $\ast$) to the center of the maze?


\begin{picture}(100,100)(0,-10) \put(0,0){\line(1,0){100}} \put(0,4){\line(1,0)... ...attern\\ continues}} \put(-5,0){$\ast$ } \put(25,-13){100 meters} \end{picture}


2. Insight is Needed for a Solution There are also many problems that probably have only one solution and a critical observation is needed just to crack the problem. In this case, ingenuity or insight makes the difference between solving the problem and not.

Example: Coffee and Milk. You are given a cup containing eight ounces of coffee and a cup containing eight ounces of milk. You transfer a spoonful of milk from the milk cup to the coffee cup. You then transfer a spoonful of the mixture in the coffee cup back to the milk cup. Assuming that both cups hold the same amount of liquid after this process, is there more milk in the coffee cup or more coffee in the milk cup ?

Example: Balls in Barrels. Ten large barrels are each filled with many golf balls which all look alike. The regular balls in nine of the barrels weigh one ounce. However, the balls in one barrel weigh twice as much as the regular balls. With one weighing on a scale that gives absolute weight, how can you find the barrel with the counterfeit golf balls ?

Example: Window Covering. A square window measures 10 feet by 10 feet. How can half of its area be covered and still leave a square opening that is 10 feet high and 10 feet wide?

3. $\cal AHA$ Solutions Mathematical training can occasionally be a liability in problem solving. That training often creates rigid patterns of thought that tend to suggest the same ideas and methods. It is essential to approach every word problem with an openness and freshness that can allow innovative ideas to percolate. This approach is typified in problems that have what the master problem collector Martin Gardner calls ``$\cal AHA$ Solutions''. These are solutions that involve a penetrating insight that reduces the problem to its essential parts. Once that insight is found, the solution appears immediately. The origins of those insights is a subject of great curiosity. The polymath Arthur Koestler wrote a provoking book called The Act of Creation to address this subject and we begin with an $\cal AHA$ Problem from his book.

Example: The Monk and the Mountain. A monk sets out from a monastery in the valley at dawn. He walks all day up a winding path, stopping for lunch and taking a nap along the way. At dusk he arrives at a temple on the mountaintop. Several days later the monk makes the return walk to the valley, leaving the temple at dawn, walking the same path for the entire day and arriving at the monastery in the evening. Is it true that there must be one point along the path that the monk occupies at the same time of day on both the ascent and descent ?

Example: The Moat An early issue of the prestigious journal Boy's Life presented this $\cal AHA$ problem. A castle is surrounded by a deep rectangular moat that is 10 feet across. A knight on a rescue mission must cross the moat, but he has only two 9 1/2-foot planks. How does he do it?

Example: The Three Lights. In one room there are three switches each connected to exactly one of three electric lamps in an adjoining room. What is the fewest number of trips between rooms needed to determine which switch is connected to which lamp?

Example: Moving Coins. Can you move three of the coins in the triangle below to make it point in the other direction?


\begin{picture}(100,60)(-5,-5) \put(0,0){\circle{8}} \put(25,0){\circle{8}} \p... ...4){\circle{8}}\put(50,35.4){\circle{8}} \put(37.5,53){\circle{8}} \end{picture}


The examples could continue for a long time, but progress in solving word problems rarely results from reading solutions. Progress comes with attempting many problems and solving a few along the way. So now it's your turn.



Reading

The following are just a few of many books with hints about problem solving and healthy collections of problems.
1.
Aha ! Insight, Martin Gardner, Scientific American Incorporated/W.H. Freeman and Company, 1978.
2.
The Act of Creation, Arthur Koestler, Dell Publishing, 1964.
3.
How To Solve It, George Polya, Princeton University Press, 1971.
4.
Problem Solving in the Mathematics Curriculum, Alan Schoenfeld, MAA Notes 1, 1983.
5.
Mathematical Problem Solving, Alan Schoenfeld, Academic Press, 1985.
6.
Teaching and Learning Mathematical Problem Solving, Edward Silver, Lawrence Erlbaum, 1985.
7.
Mathematical Quickies, Charles Quigg, Dover Press, 1985.
8.
Concepts in Problem Solving, Rubinstein, Prentice-Hall.
9.
Great Critical Thinking Puzzles and Challenging Critical Thinking Puzzles, Michael DiSpezio, Sterling Publishing Company, 1997 and 1998.


Problems In no particular order of difficulty here are some word problems for your enjoyment.
1.
Every person on earth has shaken a certain number of hands. Prove (quickly) that the number of persons who have shaken an odd number of hands is even.
2.
If a lady walks to work and rides home, it takes one and a half hours. When she rides both ways, it takes half an hour. How long would it take to walk the round trip ?
3.
Twenty people can produce four slingshots in two hours. How long will it take 15 people to make 30 slingshots ? How many people are needed to make 40 slingshots in two hours ? How many slingshots can be made by five people in 12 hours ?
4.
You are given 12 gold coins that look alike and told that one of them is a heavy counterfeit. Using a balance scale how can you find the heavy coin in three weighings ?
5.
The previous problem is no more difficult if you are told that the counterfeit is light. However, if you are told only that there is a counterfeit (but not whether it is heavy ot light) the problem becomes tricky. Can you still identify the counterfeit in three weighings ? The answer is yes, but how ?
6.
If a clock takes 5 seconds to strike 5:00, how long does it take to strike 10:00 ?
7.
At what time between 2:00 and 3:00 is the minute hand directly over the hour hand ? At what time between n:00 and (n+1):00 is the minute hand directly over the hour hand ?
8.
A car radiator has a capacity of 21 liters and is filled with an 18 percent antifreeze solution. How many liters of the solution must be drained and then replaced by a 90 percent solution to leave a 42 percent solution in the radiator ?
9.
A man arrives in a small Nevada town in need of a haircut. He discovers that there are exactly two barbers in town; one is well-groomed with spendidly cut hair, the other is unkept with an unattractive hair style. Which barber should the visitor patronize ?
10.
A woman is traveling with a wolf, a goose and a mouse. She must cross a river in a boat that will hold only herself and one other animal. If left to themselves, the wolf will eat the goose and the goose will eat the mouse. How many crossings are required to get all four creatures across the river alive ?
11.
(Tartaglia's Bride Problem) This time three beautiful brides and their jealous husbands come to a river. The ferry boat holds only two people. Furthermore, no woman may be left alone with a man unless her husband is present. How many crossings are required to get all three couples across the river alive ?
12.
Several photographers leave their camp looking for a bear. They walk 15 miles due south, 15 miles due west and sight a bear. They walk another 15 miles to return to their camp. What color is the bear ?
13.
Two half dollars rest next to each other on a table. One coin is held fixed while the other is rolled around its edge with no slipping. When the moving coin returns to its original position, how many times has it revolved ?
14.
Two friends have an 8-quart jug of wine that they want to share. They also have an empty 3-quart container and an empty 5- quart container. How can the wine be divided into two 4-quart portions ?
15.
Bronx and Brooklyn. A man has a girl friend in the Bronx and a girl friend in Brooklyn. He decides which girl friend to visit by taking the first train that arrives at his station. The trains to the Bronx and Brooklyn arrive regularly every 10 minutes. Not long after he begins his scheme the man's Bronx girl friend leaves him because he rarely visits. Why ?
16.
Two boats leave from opposite shores of a river at the same time and travel at constant but different speeds. They pass each other 700 yards from one shore, continue to the banks where they turn around. On their return trip the boats pass again 400 yards from the opposite shore. How wide is the river ?
17.
Ralph can reach his destination on time if he averages 60 miles per hour. Halfway to the destination (in distance) he realizes that he has averaged only 30 miles per hour. How fast must he travel to arrive on time ?
18.
Now generalize the previous problem. If halfway to his destination Ralph realizes that he has averaged only r<60 miles per hour, how fast must he travel to arrive on time ? If a fraction 0<p<1 of the way to his destination he realizes that he has averaged only r<60 miles per hour, how fast must he travel to arrive on time ?
19.
(High School Mathematics Contest $\sim$ 1966). ``An escalator (moving staircase) of n uniform steps visible at all times descends at constant speed. Two boys, A and Z, walk down the escalator steadily as it moves, A negotiating twice as many escalator steps per minute as Z. A reaches the bottom after taking 27 steps while Z reaches the bottom after taking 18 steps''. Find n.
20.
Four ladybugs are at the corners of a ten-inch square. At the same moment each bug begins crawling toward its neighbor to the left at the same constant rate. How far do the bugs walk before they all meet ?
21.
You overhear the following conversation:
Paul:
How old are your three children?
Paula:
The product of their ages is 36 and the sum of their ages is the same as today's date.
Paul:
That is not enough information.
Paula:
The oldest child also has red hair.
If you were Paul could you determine the ages of Paula's children ?
22.
Three boxes are labeled ``APPLES'', ``ORANGES'' and ``APPLES AND ORANGES''. Each label is incorrect. Can you select one fruit from one box and determine the correct labels ?
23.
How do you measure nine minutes with a seven-minute and a four-minute hourglass ?
24.
If five girls pack five boxes in five minutes, how many girls are needed to pack 50 boxes in 50 minutes ?
25.
Ann and Betty can do a job in ten days; Ann and Carol can do the same job in twelve days; Betty and Carol can do the same job in twenty days. How long will it take Carol to do the job alone ?
26.
Pipes A and B can fill a tank in two hours and three hours respectively. Pipe C can empty the full tank in five hours. If all pipes are opened at the same time when the tank is empty, how long will it take to fill the tank ?
27.
A 150-foot rope is suspended at its two ends from the tops of two 100-foot flagpoles. The lowest point of the rope is 25 feet from the ground. What is the distance between the flagpoles ?
28.
(Monkeys and Coconuts from Saturday Evening Post, October 9, 1926) `` Five men and a monkey were shipwrecked on a desert island, and they spent the first day gathering coconuts for food. Piled them up together and then went to sleep for the night [sic]. ``But when they were all asleep one man woke up, and he thought there might be a row about dividing the coconuts in the morning, so he decided to take his share. So he divided the coconuts into five piles. He has one coconut left over, and he gave that to the monkey, and he hid his pile and put the rest all back together. ``By and by the next man woke up and did the same thing. And he had one left over, and he gave it to the monkey. And all five of the men did the same thing, one after the other; each one taking a fifth of the coconuts in the pile when he woke up, and each one having one left over for the monkey. And in the morning they divided what coconuts were left, and they came out in five equal shares. Of course each one must have known there were coconuts missing; but each one was guilty as the others, so they didn't say anything. How many coconuts were there in the beginning ?''
29.
Two candles of equal length are lit at the same time. One candle takes six hours and the other takes three hours to burn out. After how much time will one candle be exactly twice as long as the other ? What is the answer if one candle takes six hours to burn out and the other candle takes four hours to burn out ?
30.
(High School Mathematics Contest $\sim$ 1966). ``At his usual rate a man rows downstream in five hours less time than it takes him to return. If he doubles his usual rate, the time downstream is only one hour less than the time upstream. In miles per hour, the rate of the stream is: ''.
31.
Sam knows the sum of two integers, a+b, and Polly knows their product $a \times b$. where a and b are both between 1 and 100. You overhear the following conversation:
Sam:
I don't think you can find my sum.
Polly:
I know your sum.
Sam:
I know your product.
Can you reconstruct the thinking of each person and find a and b ?
32.
A set of dominoes have the same thickness and are 1 inch wide and 2 inches long. The dominoes are stacked on top of each other with their long edges aligned so that each domino overhangs the one beneath it. If there are n dominoes in the stack, what is the largest distance that the top domino can be made to overhang the bottom domino ? How many dominos can be stacked altogether before the stack topples ?
33.
A single elimination ping-pong tournament is organized as follows: The name of each contestant is put in a hat and then names are drawn out in pairs. The people in each pair play each other with the loser retiring from the tournament. The names of the winners are once again placed in a hat and names are drawn in pairs to determine the games of the second round. The process continues until only the winner remains. If at any stage there is an odd number of names in the hat, the undrawn name remains in the hat until the next round. If N people enter the tournament, how many games are needed to determine a winner.
34.
A woman usually takes the 5:30 train home from work, arriving at the station at 6:00 where her husband meets her to drive her home. One day she left work early and took the 5:00 train, arrived at the station at 5:30 and began walking home. Her husband, leaving home at the usual time, met his wife along the way and brought her home ten minutes earlier than usual. How long did the woman walk ?
35.
Three tennis balls fit exactly (no room to spare) in a cylindrical can. Which is greater, the circumference or the height of the can  ?
36.
A broken bracelet consists of four pairs of links. It costs $10 to cut and weld a link. How can a closed bracelet of eight links be made for $30 ?
37.
A cyclist begins at the tail of a parade that is four kilometers long and starts riding in the direction that the parade is moving. By the time the cyclist has ridden to the head of the parade and returned to the tail, the parade has moved six kilometers. Assuming that the cyclist and the parade move at constant (but different) speeds, how far did the cyclist ride ?
38.
Two players alternately place identical poker chips on a large flat plate. The last player to place a chip entirely on the plate loses. What is a winning strategy for the player who moves first ?


Solutions to Examples

Solution: The Chelsea Prisoners. One method is to work step by step through the conditions and determine the minimum amount of overlap between the categories. For example, the minimum percentage of prisoners who have lost an eye and an ear is 45%. The minimum percentage of prisoners who have lost an eye, an ear, and an arm is 20%. The minimum percentage of prisoners who have lost an eye, an ear, an arm, and a leg is 15%. A simpler method is to notice that the minimum percentage of prisoners who have lost all four is 100% minus the maximum percentage of prisoners who have lost at least one of the four, which is 85% (because 85% have lost a leg). Therefore, 100% - 85% = 15% is the minimum percentage who have lost an eye, an ear, an arm, and a leg.

Solution: The Second Race. The methodical approach to this problem might use distance-velocity formulas and look at both races analytically. The intuitive approach would note that Jill runs 100 meters in the same time that Jack runs 95 meters. Therefore in the second race, Jill will overtake Jack 95 meters from the starting line or 5 meters from the finish line. In the remaining 5 meters, Jill will increase her lead and win the race.

Solution: The Maze. Of course, you could carefully add up the lengths of all the legs of the maze. Or you can note that the total area of the maze comprised of pathways is 10,000 square meters (because the thickness of the walls is negligible). Notice that each 2 square meters of the maze corresponds to 1 meter along the path. There are (10,000 square meters)/(2 square meters) = 5,000 of these 2 square meter blocks. Thus, the pathway is 5,000 meters long.

Solution: Coffee and Milk. The solution to this problem relies critically on one insight: since each cup has the same amount of liquid after the transfers are made, whatever amount of milk is missing from the milk cup has been replaced by an equal amount of coffee. By symmetry, the missing coffee in the coffee cup has been replaced by an equal amount of milk. Therefore the amount of milk in the coffee cup is equal to the amount of coffee in the milk cup. If it is assumed that the mixture in the coffee cup is stirred thoroughly before the second transfer, it is possible to solve this problem using algebra. However without this assumption, an algebraic solution is impossible, since it is impossible to know in general how the milk is distributed within the coffee. In this example, the problem as originally stated requires an essential insight for a solution. Here is another example of a problem that does not yield without a crucial observation.

Solution: Balls in Barrels. How can we assemble a collection of balls for a single weighing that will single out one of the barrels? Clearly each barrel must be sampled. Furthermore, each barrel must be sampled in a unique way so that it may be distinguished in case it has the heavy balls. Those two observations bring us to the brink of a solution. Only the final leap needs to be made. If one ball is taken from barrel 1, two balls from barrel 2, three balls from barrel 3,..., and ten balls from barrel 10, we have satisfied the requirement that each barrel be sampled in a unique way. If all of the balls weighed one gram, this collection would weigh 55 grams. In fact, the one weighing will tell us that the collection weighs 55+n grams where the n excess grams means that barrel n has the heavy balls.

Solution: Window Covering. Connect the midpoints of the four sides. The resulting square is 10 feet high and 10 feet wide and has an area of 50 square feet.

Solution: The Monk and the Mountain. The temptation for a mathematically inclined person might be to devise functions to describe the ascent and descent and then try to prove that they have an intersection point. Eventually this approach could lead to a rigorous, but rather inelegant solution. The insightful approach is to abandon the sequential thinking that the problem imposes and imagine the monk making the ascent and the descent at the same time (or imagine he has a twin brother that makes the other trip at the same time). Since both trips begin at dawn and end in the evening and since both trips follow the same path, it is clear that no matter how the monk walks on the two trips, he must pass himself somewhere along the path.

Solution: The Moat. Good story problem do not have contrived or improbable solutions, so we can eliminate ideas such as nailing the two planks together or propping them together in an unstable manner. As with most $\cal AHA$ problems, the solution is undeniable once it is seen. Try a corner!

Solution: The Three Lights. Hint: Use all your senses! Solution: Moving Coins. Hint: It can be done!