4. How Do You Do It?
Society for Industrial and Applied Mathematics eBooks · 2005
That is what learning is. You suddenly understand something you've understood all your life, but in a new way. — Doris Lessing The problems of this chapter have a slightly different flavor than those in other chapters. Whereas many problems ask how many? or how far? or how much?, the problems of this chapter simply ask how?. These are procedural or process questions, often with extra emphasis on how to do something in the most efficient way possible. The examples and exercises that follow may seem to involve little mathematics, but they do require considerable ingenuity. Furthermore, they point to several important areas of mathematics, such as optimization, operations research, and game theory, whose goal is to design optimal or winning procedures. We will proceed by way of examples that demonstrate a few typical strategies—all within the framework of Pólya's method. Example 4.1 Counterfeit golf balls. Each of ten large barrels is filled with golf balls that all look alike. The balls in nine of the barrels weigh one ounce, and the balls in one of the barrels weigh two ounces. You have a scale that measures absolute weight in ounces. With only one weighing on this scale, how can you determine which barrel contains the heavy golf balls? Solution: The key insight is that the one allowed weighing must somehow include information from all ten barrels. Furthermore, each barrel must be represented in a unique way in the weighing in order to identify the barrel with the heavy balls. There are several ways to choose the balls for the weighing. Perhaps the easiest is to take one ball from the first barrel, two balls from the second barrel, and so forth, up to ten balls from the tenth barrel. In this way, there will be 1 + 2 + … + 10 = 55 balls on the scale, which would weigh 55 ounces if all the balls weighed one ounce. However, if the 55 balls weigh n ounces over 55 ounces, it means that there are n heavy balls on the scale, which means that barrel n contains the heavy balls.