2

I have the following question: "There are n coins, all weight equally except one. In addition, we have a scale that can compare any s coins, for any s, with other s coins in the cost of w(s). The weighting informs us which sides is heavier or if their weight is equal. Describe an efficient algorithm that computes the minimal cost of finding the heavy coin".

Note: w is a positive, monotone function

My guess is that this is a dynamic programming question. However, I can't seem to find how to choose my weighting I need. Hints(or answers) will be helpful. Thank You.

M.Malone
  • 21
  • 3

1 Answers1

1

I guess dynamic programming is the correct tool for this problem.

The following approach has a flaw, but illustrates the technique.

Let $f(n)$ - minimal expected total weight of all the measurements required to find the heavier coin of $n$ coins.

$f(1) = 0$ - we know the coin already.

If we choose to compare $k$ of coins, than the probability that the false coin would be measured is $2k/n$ and after the measurement we will have $k$ coins to choose from.

Otherwise (with probability $1-2k/n$) all the selected coins are good and we have to choose from $n-2k$ coins.

$f(n) = min[w(k) + (1-2k)/n * f(k) + 2k/n * f(n-2k)]$

Dynamic programming calculates this easily.

But there is a flaw in this approach.

Suppose you have a 100 coins and you narrowed your search to 10 coins. You can choose 7 of these suspected coins and put them on one side, and on the other side you put 3 (or may be even 2) of suspected coins and 7 (or 8) of the coins you are sure are fine on the other side. Let's suppose you put 2+8 coins on the second side. Depending on the measurement result you narrow your search to 7 coins (if first side is heavier), or 2 coin (if second side is heavier), or 1 coin (if equilibrium). Who knows, may be using already verified coins will give a better result!

You should calculate the probability of each of these cases and write the expression for $f(n)$ accordingly. (That is the minimum by all $k$ not in range $[1, n/2]$ but in range $[1, n-1]$.) And make sure that if you decide to put more than $n/2$ coins on one side, you have enough verified coins to fill the second side! Argghhh, messy, but doable, just need to be accurate.

lesnik
  • 2,297