30-05-2012, 01:14 PM
MATH PUZZLES, POWERFUL IDEAS, ALGORITHMS AND COMPUTERS IN TEACHING PROBLEM-SOLVING
MATH PUZZLES.pdf (Size: 291.14 KB / Downloads: 31)
INTRODUCTION
The author’s 42 years of teaching experience has led him to the conclusion that to acquire problem-solving skills it is necessary for the students to solve many different types of problems under the guidance of a wise and experienced teacher. Just as 20 year’s experience built by repeating the same chores year after year is only worth one year’s experience, the quality and variety of problems solved by students is crucial. Nothing is gained by solving countless problems in which all the student has to do is replace variables in a formula by numbers; a few such problems suffice. What is necessary is for the teacher to collect good problems that illustrate situations that appear in many settings and to discuss such problems in great detail, including the different applications, the theories and powerful ideas that can be applied to their solution, the algorithms and associated data structures and the use of the computer as a tool for solving problems. Paradigmatic problems such as the second order system in the study of dynamics allow the teacher to introduce generally useful concepts, such as frequency response, natural frequencies, resonance, dynamic stability, and others. Teachers should constantly look for such rich paradigms.
A WINE-POURING PUZZLE
Two people want to divide evenly the wine contained in a full 8 gallon jug. They have no liquid-measuring device and the jug has no markings. However, available to them are two additional unmarked empty jugs with capacities 5 and 3 gallons. How can they measure 4 gallons?
This well-known puzzle is usually solved by trial and error either experimentally or on paper by trying ideas until one hits on the solution. To appreciate the advantages of having an organized method of solution that always works, the reader should stop reading and attempt finding a solution. The problem is relatively easy and should take no more than a few minutes to solve.
STATES
The first powerful idea that will be introduced will be the idea of the state of a system.The state concept is very important in applied mathematics and central in computer science as it appears in such basic concepts as finite-state machines including Turing Machines and algorithms. We will not give a formal definition of state but rather will illustrate the idea in the context of the puzzle at hand. If the reader has either solved the problem or at least seriously attempted a solution, it should be clear by now that the four gallons could be measured as a result of pourings between the jugs. Since none of the jugs are marked, the only meaningful situations are those in which, taking a jug containing some wine, pourings are made to other jugs until either the jug being poured into is full, or the jug from which the pouring is done is empty. Intermediate situations are indeterminate. We can describe the condition or state of the system by means of three ordered numbers indicating the amount of wine in each of the 8, 5 and 3 gallon jugs. The initial state is given by (8, 0, 0). There are only two states that can be reached in one pouring from the initial state. To arrive at the first one the wine in the 8 gallon jug is poured into the 5 gallon jug until it fills up.
ENTER THE COMPUTER
Building the graph of Fig. 2 can be laborious, and it definitely would be very laborious for analogous puzzles where the capacities of the jugs are larger numbers such as 69, 37 and 32. In such cases we can resort to use a computer to do the work for us. In this introductory presentation we will only go as far as attempting to obtain a structured list of states. This is a reasonable decision since a very large complicated graph is not much of use since it is very easy to loose sight of the connecting lines. We will start with the original state (8,0,0) and list in the same line those states that can be reached in one pouring. Then we process each of these new states starting a line with each one of them and listing in the same line those states which, not having appeared before, can be reached in one pouring.