You have fifteen identical-looking coins. One of the coins is counterfeit and weighs more than the other coins.

Question

You have fifteen identical-looking coins. One of the coins is counterfeit and weighs more than the other coins. The only scale available is a balance scale. This scale lets you put any number of these coins on either side and will determine which side is heavier or if the sides are equal. What is the fewest number of times you need to be able to use the scale to find the counterfeit coin (assuming you might have bad luck when picking which coins to weigh)? Name the heuristic used.

Please help me as soon as possible!

Answer 1

You split the coins into three even piles (so 5 coins each). You pick two of the piles, A and B, and weigh them. There are two potential outcomes:

(1) Piles A and B are equal weight. Then pile C must contain the counterfeit coin, because there is only one counterfeit coin and if it was in pile A, then pile A would be heavier then pile B (and vice-versa if it was in pile B). Or

(2) Piles A and B are not equal weight. Then the heavier pile must contain the counterfeit coin. (See above logic.)

You can now remove the two piles that do not contain the counterfeit coin, and you are left with only 1 pile (5 coins).

You can continually repeat this process, and each time you will be left with one third the coins, i.e. ceil(n/3) where n is number of coins, and ceil if the ceiling function.

Step 0: 15 coins

Step 1: 5 coins

Step 2: 2 coins

Step 3: 1 coin

It will take 3 measurements.

The heuristic here is similar to divide-and-conquer method used by many recursive/iterative algorithms like binary search, although I'm not sure if you class or teacher has a more specific name for it. e.g. In binary search, you constantly reduce the available options by ceil(n/2) - 1 each step.