The other day I was reading a puzzle book and found this classic: There are 9 coins on the table, but one of them is fake and weighs slightly less (or more, doesn't matter). How many measures do you have to make to be sure you know which coin is the fake one? This is not so hard, but the problem is the book forgot to mention there are nine coins, so I tried to solve it for an n number of coins (there is only one fake and n-1 real). I'm trying to find out an algorithm as simple as possible to find out the answer.
Answer
If you know the fake is lighter, then, using N weighings, you can find the fake among
at most $3^N -1$ real coins.
To do that, you need to use a ternary search:
Split the coins in three stacks, as equally as possible. Pick two of the stacks having the same number of coins, and compare them. If one of the stacks is lighter, that stack has the fake. If the stacks are equal in weight, the third stack has the fake.
Repeat until you are down to a single coin.
This method has the optimal worst-case limit, since each of the possible weighing result is assigned to a different conclusion. Indeed, when the number of real coins is exactly the maximum, this is the only method that is guaranteed to find the fake.
No comments:
Post a Comment