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.
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.
Not sure how to express this entirely mathematically:
The solution being X number of iterations of the right side of the equation until it is true.
1 = ((n / 3) then round up)
Divide by 3 because each weighing, we divide the coins into 3 groups as equally as possible and weigh two of them. If they weigh the same, the coin is in the unweighted group. The rounding is to account for the worst-case scenario, if the groups are slightly unequal in number of coins and the fake coin is always in the bigger group.