The Probabilistic version of the Counterfeit Coin Problem

The DP functional equation for this version of the problem is as follows:

f(n,k) = min { (2s/n)f(s,k+1) + ((n-2s)/n)f(n-2s,k+1): s in D(n) } , n =2,3,...,N; k=0,1,2,..,cf(0,k) = f(1,k) = 1 , k<=c

f(n,c+1) = 0, n=0,1,2,...,N

D(n): = {1,2,...,Int(n/2)}

The f(n,k) entry is located in row n and column k. Recall that n = the number of coins left for inspection; and k = number of weighings that have already been conducted. Thus, if you want to solve a problem with N coins, the probability of failure is given by f(N,0).

Back to Excedent front page