The counterfeit Coin Problem

# MiniMaxy

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 number of weighings required for the indentification of the the counterfeit coin under the "worst case scenario", namely assuming that Mother Nature is playing agains us, hence Dr Pessi is in charge.

DP approaches the problem by introducing two innocent looking definitions which underly its "if-then" strategy:

 f(n) := number of weighing under an optimal policy given that we have n coins to inspect. f(n | s) := number of weighing under an optimal policy given that we have n coins to inspect and that we decide to put s coins on each side of the scale in the current weighing.

Then clearly, the following must be true:

 f(0) = 0 f(1) = 0 (1) f(n) = f(n | s) , for some s in D(n), n>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) f(n) = min { f(n | s) : s in D(n) }, n>1.

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.

For this purpose it would be instructive to look again at the picture representing the if-then process. So here it is:

Thus, it follows that f(n|s) is equal to either 1 + f(s) or 1 + f(n-2s). This is so because there are only two possible outcomes if we place s coins on each side of the scale given that we have n coins to inspect. Either the counterfeit coin will be on the scale, in which case we shall have to inspect s coins, or it will be off the scale in which case we shall have to inspect n-2s coins. The 1's in these expressions represent the "charge" for the current weighing.

But Given that Dr Pessi is handling this case, we should plan our strategy on the worst case scenario of the "if-then game". Thus, we conclude that for n > 1 we have

 (3) f(n | s) = max {1 + f(s) , 1 + f(n - 2s) } = 1 + max { f(s) , f(n - 2s) }

So combining (2) and (3) we obtain the following typical DP functional equation for n > 1:

 f(n) = min {1 + max {f(s) , f(n - 2s) } : s in D(n)} (4) f(n) = 1 + min { max {f(s) , f(n - 2s) } : s in D(n)}

We can go one step further: it is not difficult to show (try doing it on your own) that f(m) is not decreasing with m, hence

 (5) max {f(s) , f(n - 2s) } = f( max {s , n - 2s} )

Hence, (4) can be rewritten as follows:

 (6) f(n) = 1 + min { max {f( s , n - 2s) } : s in D(n)}

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 m = 2,3,...,n - in this order - determine the value of f(m) according to (6), namely

 (7) f(m) = 1 + min { max { f(s) , f(m-2s) : s in D(m) }

The algorithm will produce a report consisting of the following three columns:

 m f(m) D*(m)

where D*(m) denotes the set of optimal values of s found while computing f(m). There is a facility to display the details of the right-hand side of (4) for any value of 1 < m <= 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 (4) takes the following form

 f(4) = 1 + min { max { f(s) , f(4-2s) : s in {1,2} }} = 1 + min { max {f(1) , f(4-2)} , max { f(2) , f(4-4) }} = 1 + min { max {f(1) , f(2) } , max {f(2) , f(0) }} = 1 + min { max {0 , 1} , max {1 , 0} } = 1 + min { 1, 1 } = 1 + 1 = 2 , D*(4)={1,2}

Thus,

 m f(m) D*(m) 0 0 -- 1 0 -- 2 1 {1} 3 1 {1} 4 2 {1,2}

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 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) f(m) = min { cost(s) + max {f(s) , f(m-2s)} : s in D(m) } m = 2, 3, ..., n

In fact, we may as well allow the cost to depend also on how many coins are still be inspected (m), in which case the functional equation would be as follows:

 (9) f(m) = min { cost(m,s) + max {f(s) , f(m-2s)} : s in D(m) }} m = 2, 3, ..., n

Needless to say,in both of the above extensions we have f(0)=f(1)=0. Further more, under normal conditions (on cost), it would be possible to establish that f(m) is nondecreasing with m, hence (9) could be rewritten as follows:

 (10) f(m) = min { cost(m,s) + f( max{s,m-2s})} : s in D(m) }} m = 2, 3, ..., n

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.

 Give it a try!

## Disclaimer

If cost(n,s) = 1 for all n and s, as well as in other special cases, it is possible to solve the problem analytically in "closed-form". In fact, we strongly encourage you to do it and hopefully we shall have time soon to webify this approach solution.

We do not suggest here that DP's numeric approach is superior to the analytical solution. We merely use this problem to illustarte how DP works.