First of all there is considerable impatience with the material. Surprisingly, this is often noticeable in the better students. But better students tend to demand instant understanding. Mathematics has always been easy for them. Understanding and intuition have come cheaply. Now as they move into the higher reaches of mathematics, the material is getting difficult. They lack experience. They lack strategies. They don’t know how to fiddle around.
— Davis and Hersh in "The Mathematical Experience", 1980
Davis and Hersh are talking about students from the late 1970’s, but the passage describes quite accurately the resistance displayed by some of my university students even in this century.
I particularly like the comment about fiddling around, because that’s what you have to do to create a proof or solve an unfamiliar problem. Throughout my teaching career, whatever the curriculum of the day was, my students seemed to have had very little practice fiddling around. They seemed to have the notion that a solution or proof always follows a pre-ordained script.
I was able to remedy this somewhat by exposing them to mathematical puzzles—ones that were simple, yet which could not be solved by following a memorized procedure. The students pretty well had no choice except to fiddle around. And because the puzzles seemed simple, they were quite willing to try.
I ended the previous post with the following puzzle. It’s simple, but the complete solution is not obvious. It’s one that I frequently used in a university course, and I think it would work for junior high / high school students. Although it is well known, I doubt that many students are familiar with it.
You are presented with eight coins, numbered from 1 to 8, but otherwise identical in appearance. One of them is fake and weighs slightly more than the others. The real coins are all exactly the same weight.
You have at your disposal a two-pan balance, and no other weights except the coins themselves. The problem is to find the counterfeit coin using as few weighings as possible.
Now if you choose two of the coins and by good fortune one of them was the counterfeit, then weighing one against the other would reveal it. However, this really does not count as being a solution. You need something that works all the time and does not depend upon luck.
Here is a possible solution, one that is based on the binary search idea described in my previous post. This is how I did it at first, and so did most of my students.
Divide the eight coins into two groups of four. Weigh one group of four against the other to find out which group contains the fake. Divide that group in half, and weigh two against two to identify which pair contains the fake. For the third and final weighing, compare the coins in that pair to identify the counterfeit.
A binary search is very efficient in many cases, as it is for this puzzle. But it is a script to be followed, and following a script does not always lead to an optimal solution. We have yet to convince ourselves that three weighings is the best that we can do, that it is impossible find the counterfeit in less than three weighings. There doesn’t seem to be an obvious way to prove this, so here’s where the fiddling around has to occur. And we will see how fiddling around reveals a better solution.
A tactic that is sometimes useful is to approach a problem from the reverse direction. Instead of trying to find the minimum number of weighings for eight coins, let us ask what is the maximum number of coins we can handle if we are only allowed one weighing. If we have a collection of coins and one is fake and slightly heavier, how many coins can be in the collection? Can we find the counterfeit with one weighing if we have two coins? three coins? four coins? etc.
If we have two coins and one of them is fake, putting a coin in each pan will immediately identify the counterfeit. If we have four coins and one is fake, putting two in each pan will allow us to identify which pair contains the fake, but unfortunately it does not reveal which member of the pair is the fake. We would need another weighing.
So one weighing with four coins (or more) seems out of the question. What if we have three coins? Putting two in one pan and one in the other won’t help. The coins are close in weight, so the pan with two coins would tilt down regardless. So, it is unreasonable to ask about an odd number of coins—we need an even number so that we could put the same number in each pan.
One of the difficulties that I have when fiddling around is that I am prone to making unwarranted assumptions, and I just made one here. Who says that we have to put all of the coins in the pans? With three coins, why not see what happens if we put one coin in each pan and leave the third coin aside? And that does it! If the balance tilts, we will know immediately what coin is counterfeit. If the balance stays level, then the two coins in the pans must be the same weight and so the coin that we left aside must be the counterfeit. With three coins we can find the counterfeit with one weighing.
This fiddling around with three coins throws a new light on the entire puzzle. Maybe we don't have to divide the eight coins into two groups of four. What if we divide the eight coins into three groups, put a group in each pan, and leave the third group aside?
What if we put three coins in each pan and leave two aside? If the pans don’t balance, this will tell us which group of three contains the fake. If the pans balance, this will tell us that the group of two that we left aside contains the fake. Either way, we will know which group contains the counterfeit, and since the groups contain only two or three coins, with one more weighing we can find the counterfeit.
So this logical fiddling around leads to a better solution. With eight coins, we can find the counterfeit in two weighings, and the fiddling around has revealed that the counterfeit cannot be found with less than two weighings.
* * *
In its original form, the counterfeit coin puzzle did not use numbered coins. The reason I specified that they be numbered is that there is another solution, and it’s easiest to explain if you number the coins. This alternate solution came about because I was still fiddling around and changed the question a bit. What if we could not use the information obtained from the first weighing to determine what to do for the second weighing? In fact, a solution with two weighings is also possible in this case.
Let us imagine that the coins are arranged in an array as follows:.
Using the rows: weigh 1, 2, and 3 against 4, 5, and 6, and leave 7 and 8 aside. That will tell us which row of the array contains the fake. Call it the hot row.
Using the columns: weigh 1, 4, and 7 against 2, 5, and 8, leaving 3 and 6 aside. That will tell us which column is the hot column.
The counterfeit coin is located at the intersection of the hot row and the hot column, just like finding a point in the Cartesian plane given its x and y coordinates. And we don't have to know the outcome of the first weighing before doing the second weighing.
* * *
You can search the internet and find this and many other counterfeit coin puzzles. You will no doubt encounter the problem discussed here. Some posts ask why use eight coins when the same solution works for nine. I think that using nine coins gives too strong a hint that the coins should be split into three groups of three, so I prefer the eight coin version.
* * *
It would be wonderful if there was an algorithm that always tells us how to fiddle around.
Unfortunately, there is as yet no such algorithm. The closest I have seen to this is the collection of strategies described by George Polya in his books about problem solving. What one should do when fiddling around depends upon what the problem is. The best way to learn is to practice on lots of problems.
No comments:
Post a Comment