Finding the two different coins

 

Here is the problem:

You have n coins where n = 2^k for an integer k such that n − 2 coins are of the same weight and two coins weigh more than others. Two heavier coins may be of the same weight, or their weights may be different. You have a balance scale: you can put any number of coins on each side of the scale at one time, and it will tell you if the two sides weigh the same, or which side is lighter if they do not weigh the same. Outline an algorithm for finding the two heavier coins using O(log n) weighings.

I know the answer if there is only one coin that is different than others. And I also found similar question where the different coins are known to be heavier.

Given n coins, some of which are heavier, find the number of heavy coins?

Any help.

Suppose you split the coins into two piles of 2k-1 coins.

  • If the two piles weighed the same, then you know that each pile must contain one of the heavier coins, and both heavier coins weigh the same. Use your "one heavier coin solution" on each pile.
  • If the two piles do not weigh the same, split the lighter pile into two piles with 2k-2 coins. The idea here is that we do not yet know if the heavier pile has both heavy coins or if the piles have one each (and the heavier pile has the heaviest coin), and we'll use the second weighing to find out which.
  • If those two piles do not weigh the same, then both of the piles of coins from the first weighing must have one heavy coin each (and the two have different weights). Use your "one heavier coin solution" on each pile.
  • If those two piles do weigh the same, then both heavy coins had to be in the heavier pile of 2k-1 coins. Recurse on that pile. (and we'll figure out whether the two heavy coins weighed different later).

    • Now, for the proof of the number of weighings.

    Assuming we never use the "one heavy coin solution", this setup will in the worst-case take two weighings to cut the search space in half. Thus, the number of weighings here is 2 log n .

    Note that we use the "one heavier coin solution" at most twice. Thus, a loose upper bound is 2 log n from the above two steps, plus 2 times the number of weighings for the "one heavier coin solution", which gets us 2 log n + 2 * O(log n) , which is still O(log n) .

    链接地址: http://www.djcxy.com/p/70674.html

    上一篇: 如何从8个硬币中找到假币

    下一篇: 找到两个不同的硬币