The Counterfeit Coin problem is a fascinating puzzle. It has a number of interesting features which make it an ideal teaching tool. We shall mention but a few:
- It is very easy to describe the essence of the undelying problem in English - or for that matter any other spoken language
- It has many versions of various degrees of complexity. Some are very easy, others are very difficult to solve, still others are intractible.
- Some of the versions are (mathematically speaking) not well defined.
- Some of its versions are easier to solve than formulate (mathematically)
In short, it is a small treasure.
In this directory we consider four relatively simple versions of the problems. In fact, one is trivial. Our main interest is to show how DP handles such problems, that is we use this puzzle as a tool of thought for teaching DP.
We shall first describe the problem roughly, and then refine it and introduce the four simple versions of interest. If you are already familiar with this problem you may wish to move directly to the DP modules.
The story goes like this:
You are given a collection of n coins all but one of which have the same weight. It is known that the odd (counterfeit) coin is heavier than the other coin. You are also given a balance-beam: a device that can check whether or not two collections of coins are equal in weight, and if they are not, which one is heavier than the other. Note that this device cannot measure the weights the two collections - it can only determine which one of the two collections is heavier, if any.
Your mission in life is to plan a weighing scheme so as to identify the false coin with as few weighings as possible.
Before we rush to solve this problem let us explain why this is mission impossible and why some refinements are necessary. Suppose then that two persons, say Romeo and Juliet, are competing for the best weighing plan for this problem and that you are the judge. For simplicity assume that there are 101 coins one of which is a counterfeit. How would you decide whether Romeo's plan is better than Juliet's - or vice versa?
There are a number of difficulties. We shall mention only the obvious one: there is a very strong element of chance in this enterprise, so the competition will have to be conducted a number of times. Typically, Romeo will win some of the races, Juliet will win some, and there could be a number of draws. It is not obvious therefore what rules you should use to determine the winner. In fact, it is not clear how many times the race should run.
The difficulty is much more serious if the competition is conducted mathematically, because in this case it would be necessary to simulate "chance " mathematically and this leads to a number of fundamental questions such as : who decides where the conterfeit coin will be as the "virtual" weighings are conducted? What is "best" in such an uncertain environment?
OK. This is almost as far as we can go without becoming too techy. If you are statstically oriented, you must have noticed that the difficulty here is that we are trying to optimize a random variable associated with a stochastic process. This, needless to say, is mission impossible.
In short, to progress mathematically in this area we need to do two things:
- Quantify the uncertainy underlying the weighing process
- Formulate a well definie optimality criterion
To handle the first we invite Mother Nature to the party and let her decide where the conterfeit coin will be placed as the weighings are conducted.
Now, it is well known in mathematical circles that Mother Nature is ver busy so invariable She sends one of her assistances to handle cases of this type. There are three assistances: Dr Opti, Dr Pessi and Prof. Laplace.
Dr Opti is the representative of the eternal optimimists among us: she always decides in favour of the competitors. So regardless of what your weighing plan is, Dr Opti will make sure that the false coin is placed in the smallest collection yet to be inspected. For example, if there are 101 coins to ispect and you decide to put 40 coins on each side of the scale, then Dr Opti will make sure that the counterfeit coin is the one not on the scale. As a consequence, the scale will be balanced, and it will become obvious that the counterfeit coin is not on the scale, in which case 21 coins will be left for inspection.
Unfortunately, from a mathematical point of view playing the counterfeit coin game with Dr Opti is a very boring business: the best policy is to put two coins on the scale, one on each side. The game is over in one weighing. If you really want to enjoy the game, play against Dr Opti: try to formulate a policy that will prolong the weighting process as much as possible.
Dr Pessi represents the pessimists among us: his policy is to play against you. Not that he is a bad guy or that he has something personal against you. Not at all. He is acting this way simply because he believes that this is good preparation for life. He might have a point there.
Although Dr Pessi is always playing against you, not all is lost. In fact, because of his extreme single mindedness he is completely predictable and therefore there is essentially no uncertainty when you play against him in that you can predict his decisions, or more precisely, the consequences of his decisions. For example, if there are 101 coins to inspect and you place 40 coins on each side of the scale, the Dr Pessi will certainly make sure that the counterfeit coin is on the scale. Thus, in the next weighing you'll have to deal with 40 coins.
Another way to describe the game we play with Dr Pessi is to say that this is a minimax game: we are trying to minimize the numer of weighing and Dr Pessi is trying to maximize the number of weighing. It should be an interesting game!
Prof. Laplace has a different attitude altogether. He adheres to what he coined way back in 1825 the Principle of Insufficient Reason. In the context of our problem it dictates that if you have a collection of k coins to inspect and one of them is a counterfeit, then each of the coins in the collection is equally likely to be the counterfeit coin. Thus, if there are 101 coins to inspect and you decide to put 40 coins on each side of the scale, the experiment will be governed by a process that will put the counterfeit coin on the scale with probability 2x(40/101) = 80/101. The probability that the counterfeit coin will not be on the scale is therefore equal to (101-2x40)/101 = 21/101.
In summary, playing the game against (with ?!?) Dr Opti is a simple, boring and very short event. We shall therefore not consider it any further. The game against Dr Pessi is more of a challenge, but still relatively simple because we can predict the consequences of his decisions. The inherently stochastic process that we started with is transforming into a deterministic one. We shall sove this puzzle under this conditions using DP. The situation with Prof. Laplace's game is different, as in this case the weighing process is stochastic in nature: we have to consider the probability that the counterfeit coin is on the scale and the probability that the counterfeit coin is off the scale. Thus, in this case we have to consider the issue of optimality criterion.
This is neither the place nor the time to go into details concerning what kind of optimality conditions are suitable for situations of the kind similar to the Counterfeit Coin Problem. We shall simply adopt two sort of standard approaches, to wit:
- Minimization of expected value
- Minimization of probability of excedent
Under the first our mission is crystal clear: our aim is to minimize the expected value of the number of weighing required to identify the counterfeit coin. The second is more problematic. it says: minimize the probability that the number of weighing required to identify the counterfeit coin is greater than or equal to some constant c. Thus, to use this criterion we have to decide what value of c should be used. This could be an extremely subjective decision.
So we introduced four versions of the problem: two deterministic versions (Dr Opti and Dr Pessi) and two stochastic versions (Expectation and Probability of Excedent with Prof. Laplace). The first is trivial so we shall not examine it any further.
If you are interested in a really difficult version of the problem consider the case where there are k counterfeit coins in the collection, and the objective is to identify all of them, where k is a given number. And if you really want to solve a very difficult problem consider the case k is not known in advance.
We provide DP modules for the following versions of the counterfeit coin problem :
- Playing Minimax with Dr Pessi
- Playing Expectation with Prof. Laplace
- Playing Probability of Excedent with Prof.Laplace
It will be useful, however, to first examine the DP Perspective on this puzzle.