Fake Coin Problem

19,677

Solution 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.

Solution 2

The "decrease by 3" algorithm works on the principle that you can reduce the set of marbles you have to compare by 1/3 by doing only 1 comparison.

Split the marbles into 3 groups, and weight 2 of them, say group 1 and 2.

  1. If weight of group 1 == weight of group 2 then group 3 has the fake marble
  2. If weight of group 1 < weight of group 2 then group 1 has the fake marble
  3. If weight of group 1 > weight of group 2 then group 2 has the fake marble

Of course this assumes that the original set of marbles can be split evenly into 3 groups. If that's not the case then split into 3 groups evenly ( each group has the same number of marbles ) and keep the remaining ( 0,1, or 2 ) marbles on the side and add them back to the group of marbles you have to consider after the comparison step.

Share:
19,677
Boris Kleynbok
Author by

Boris Kleynbok

Updated on June 29, 2022

Comments

  • Boris Kleynbok
    Boris Kleynbok over 1 year

    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.

  • Valmond
    Valmond over 12 years
    This is one of my favourite problems I stumbled onto and 3 weights is doable but I never thought about a 'generic algo' so solve it. BTW, splitting in three parts is the way to start with, depending on the result you will need to choose differently afterwards. The worst is of course when you have a difference, say 1234 'heavy' and '5678' light. The thing to remember is that 1234 can't be 'light' and 5678 cant be heavy. and of course that 9,10,11,12 Must be neither. Oh shite, I thought it was the problem when the fake coin is Different (ie. lighter or heavier). Sorry.