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 probability that the total number of weighings required for the indentification of the the counterfeit coin will exceed a given value c.This is the most difficult version of the Counterfeit Coin Problem that we examine. We therefore suggest that if you have not done it already, you should read the material on the other two versions before you proceed. We also assume that you are familiar with the notion of conditional probabilities and conditional expectation.
Ovserve that in this version of the problem we assume that Chance is represented by Mother Nature, which in turn is represented by Prof. Laplace. Hence all the coins yet to be inspected are equally likely to be the counterfeit coin.
So far so good!
The DP approach to this problem is as follows: we start with two innocent looking definitions:
Then clearly, the following must be true:
The first two observations are trivial so let us examine the last two, starting with the third one. It says the obvious: if we are to do the best we can given m>1 coins given that we have already conducted k > c weighings, then clearly we have already exceeded the critical value c and therefore the probability is 1 that we shall exceed it at the end of the process.
The last observation is more subtle. It argues that given the situation (n,k,c) 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 the 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,k|s) for all s and then choosing the smallest value.
In other words, the above innocent looking definitions entail the following
(1) All we have to do now is find a way of expressing the value of f(n,k|s) in terms of values of f(m) for values of m < n. For this purpose it would be instructive to re-examine the following picture
This is just a reminder that there are only three places to place the coins: A coin is either on the left-hand side of the scale or the right-hand side of the scale or off the scale. And since the first two events are equivalent from our point of view, we can manage with the following two events:
- The counterfeit coin will be on the scale after the current weighing
- The counterfeit coin will be off the scale after the current weighing
The following table summarises the situation with regard to the two events that can be generated by (n,s,k):
The two events that can be generated by (n,k,s)
Event Probability of event Probability of failure* CFC is on the scale
2s/n
f(s,k+1)
CFC is off the scale
(n-2s)/n
f(n-2s,k+1)
CFC = "Counterfeit Coin" ; "failure" = Identifying the counterfeit coin in no more than c weighings.
In short, f(n,k|s) is equal to the expected value of f(n',k+1) where n' is the number of coins left for inspection after the current weighing. n' is a random variable that can take two possible values, namely either s or n-2s, with probabilities 2/n and (n-2s)/n, respectively. Thus,
(2) If we then combine (1) and (2), we obtain the following DP functional equation:
(3) It can be translated into English as follows:
If we have n>1 coins to inspect then the best we can do is put s coins on each side of the scale and the do best we can with regard to the coins that will be left for inspection after the weighing. The optimal value of s is determined by computing the conditional probability of excedent for all feasible values of s according to Prof. Laplace's probabilities.
Observe that we are interested in computing the value of f(N,0).
The DP algorithm we use to solve the problem can thus be stated as follows:
Algorithm
Step 1: Initialization
Set
f(n,c+1) = 1, for all n=0,1,2,3,...,NStep 2: Iteration
For k = c,c-1,...,0 - in this order - DO:
f(0,k)=f(1,k) = 0
For n = 2,...,N determine the value of f(n,k) according to (1)-(3).
Namely, compute
(4) The algorithm produces a report consisting of a table whose rows represent n and whose columns represent k. The entries are the values of f(n,k). The sets of optimal solutions for the (n,k) pairs are also presented in the table. The elements of these sets are enclosed within curly brackets.
The following is a small table generated for the pair (n=5, c=2).
n\c 0 1 2 0 0 , {} 0 , {} 0 , {} 1 0 , {} 0 , {} 0 , {} 2 0 , {1} 0 , {1} 1 , {1} 3 0 , {1} 0 , {1} 1 , {1} 4 0 , {1,2} 1/2 , {1} 1 , {1,2} 5 0 , {1,2} 3/5 , {1} 1 , {1,2} To illustarte how the algorithm works, let us pretend that we have already computed the values of f(n,k) for all n=0,1,2,3 and k=0,1,2. We shall now compute the value of f(4,1) according to (4).
where D*(n) denotes the set of optimal values of s found while computing f(n,k). In due course there will be a facility to display the details of the right-hand side of (4) for any (n,k) pair.