Fake Coin Problem

Question

Classic problem with 12 coins ( or marbles) one of which is fake. Fake coin assumed to be lighter than real one.

Having scales to compare coins (or marbles).

One can do comparison one by one and compare all 12 coins.

More efficiently one can do it using Decrease By Factor algorithm. Which is divide the coin stack by 2 and compare 2 stacks on the scales.

Big O of the decrease by factor 2 is log2n.

There is more efficient decrease by factor 3 (log3n) algorithm but I have not yet found it.

If anyone explains it and why it is more efficient let me know.

Answer 1

The main idea here is to use more knowledge of the problem in setting up your test: If you separate into 3 instead of two stacks and do a weighing with two of those stacks (each containing the same number of coins), you can have only two cases given that the single fake coin can be in only one of these three stacks:

1.) Both sides have identical weight: the fake coin cannot be in the two stacks weighed, so must be in the 3rd: you reduced the problem space to 1/3

2.) One side weighs more than the other: since there is only one fake coin it must be on the side that weighs less: again you reduced the problem space to 1/3

Rinse and repeat.