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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Not a duplicate (of that one, at least), here we know in advance that the fake is lighter. $\endgroup$– BassCommented Mar 9, 2018 at 13:16
-
$\begingroup$ The question makes no mention of what we are measuring with. $\endgroup$– LeppyR64Commented Mar 9, 2018 at 13:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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.
-
$\begingroup$ This does not give the perfect answer. Let's say we have 9 coins. It is possible with two. According to your formula, 3*3-1=8, two are not enough $\endgroup$ Commented Mar 9, 2018 at 13:46
-
$\begingroup$ @FluffyUnicorn there are 8 real coins in that case, aren't there? $\endgroup$– BassCommented Mar 9, 2018 at 13:52
-
$\begingroup$ @FluffyUnicorn I was confused too. The question is how many weighings does it take, and you've spoilered out the number of coins and left the number of weighings plain. Your answer is 100% correct, just arranged in a weird way :) $\endgroup$– LeppyR64Commented Mar 9, 2018 at 14:01
-
$\begingroup$ @LeppyR64 Trust me, ceiling functions of logarithms would have been way weirder :-) $\endgroup$– BassCommented Mar 9, 2018 at 14:07
-
$\begingroup$ Ohh, that's right, I didn't see the real. Thank you $\endgroup$ Commented Mar 9, 2018 at 14:26
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ You are assuming that you have a two pan balance scale. Since the question does not mention this, it should be part of your answer. $\endgroup$– LeppyR64Commented Mar 9, 2018 at 13:24
-
$\begingroup$ That's a good answer. Mathematically I would say floor(N/3)+Nmod3. Not sure though. $\endgroup$ Commented Mar 9, 2018 at 13:53