So we have this collection of N coins and we know that all but one of the coins have the same weight and that the counterfeit coin is say heavier than the other. We have to find a weighing plan that will minimize the expected value of the number of weighings required for the indentification of the the counterfeit coin, assuming that we play the game against Porf. Laplace.
If you have not done it already, read the material on the Minimax model before you proceed. The model discussed here is a bit more complicated.
DP approaches the problem by introducing two innocent looking definitions which underly its "if-then" strategy:
Then clearly, the following must be true:
(1) The first two observations are trivial so let us examine the third.
It says the obvious: if we are to do the best we can given n > 1 coins, then we shall have to do two things. Firstly we shall have to put some coins on the scale, say, s of them on each side, and then we shall have to do the best we can with the situation we shall face after we complete this weighing. Of course, this does not help us much because we do not know the magic value of s for which the above equation is valid.
On second thought we observe that the magic value of s can simply be determined by enumeration, namely by evaluating f(n|s) for all s and then choosing the smallest value.
In other words, the above innocent looking definitions entail the following
(2) All we have to do now is find a way of expressing the value of f(n|s) in terms of values of f(m) for values of m < n. This is not too difficult because we know that given (n,s), after the weighing we shall be left with either s coins or n - 2s coins, depending on whether the counterfeit coin is on the scale or off the scale respectively. Thus, all we have to do is compute the respective conditional probabilities and then the expectation.
Let's then compute the conditional probabilities wwhich we denote as follows:
For this purpose it would be instructive to look again at the picture representing the if-then process. So here it is:
Since according to Prof. Laplace's dictum each coin has the same probability of being the counterfeit coin, P(on| n,s) is equal to the proportional to the number of coins on the scale (s) and P(off| n,s) is proportional to the number of coins off the scale (n-2s). Thus,it follows that
(3) (4) For example, if n=20 and s=6, we have P(on | 20,6) = 12/20 = 6/10 and P(off | 20,6) = (20-12)/20 = 8/20 = 4/10. Note that the two probabilities sum-up to 1, as they always should.
The situation can be summarised as follows:
We have n coins to inspect and now we place s coins on each side of the scale
Event Probability of event Expected value of the cost of the event CFC is on the scale
2s/n
1 + f(s)
CFC is off the scale
(n-2s)/n
1 + f(n-2s)
CFC = "Counterfeit Coin".
Thus, multiplying the costs by the respective probabilities and addting the products we obtain the following:
(5) So this is the end of the story, as combining (1),(2) and(5), we obtain:
(6) The DP algorithm we use to solve the problem can thus be stated as follows:
Algorithm
Step 1: Initialization
Set f(0) = f(1) = 0.Step 2: Iteration
For n = 2,3,...,N - in this order - determine the value of f(m) according to (6), namely
(7) The algorithm will produce a report consisting of the following three columns:
n f(n) D*(n) where D*(n) denotes the set of optimal values of s found while computing f(n). In due course there will be a facility to display the details of the right-hand side of (6) for any value of 1 < n <= N.
Let us compute the first 5 rows of the table by hand. As we explained above, from the definition of f(m) it follows that f(0)=f(1)=0. In fact, m=0 and m=1, the set of feasible values of s, denoted above by D(m) is empty.
The next two rows are almost as easy, as it is clear that for m=2 and m=3 we have D(m)={1}, namley there is only one feasible decision. Hence this decision optimal. Thus, D*(m)={1} and f(m)=1 for m=2 and m=3.
Consider now m=4. In this case D(4)={1,2}, hence (6) takes the following form
Thus,
m f(m) D*(m) 0 0 -- 1 0 -- 2 1 {1} 3 1 {1} 4 3/2 {1} One last comment:
it is not too difficult to imagine situations where one is charged for each weighing and the objective is to minimize the expected value of the total cost of the weighings. If we let cost(s) denote the cost charged for a weighing where s coins are placed on each side of the scale, then DP equation equation will be of the following form:
(8) In fact, we may as well allow the cost to depend also on how many coins are still be inspected (n), in which case the functional equation would be as follows:
(9) We plan to extend our DP code to support this extension. For the time being you'll have to manage with the standard version of the problem.