You have 12 identical coins,
and one of them is fake. The fake could be either heavier or lighter than the others, you don’t know. Could you find out which one is fake just with 3 tries on the balance scale?
Got this from one of my computing friend, but I couldn’t solve it.
August 12th, 2005 at 6:24 am
split it into 2 halves.Randomly choose one of the halves, split into 2; 3 pieces a group, and weight it. If it is equal, then the odd piece is in the other halves. …hai…sigh..don’t know how to explain! give up!
August 13th, 2005 at 9:16 pm
Ok, this answer provided by my friend who solve it in 30 minutes. I must admit defeat.
Label coins as A-L.
Step 1: compare 4 coins (ABCD) with another 4 (EFGH)
———————————
*If they are equal, then the fake is one of IJKL. ABCDEFGH are not fake.
Step 2: compare IJ with either 2 of ABCDEFGH.
**If they are equal, then the fake is one of KL. IJ are not fake.
Step 3: compare K with either one of ABCDEFGHIJ.
If they are equal, then L is fake.
Else, then K is fake.
**If IJ and 2 of ABCDEFGH are not equal, then the fake is one of IJ. KL are not fake.
Step 3: compare I with either one of ABCDEFGHKL.
If they are equal, J is fake.
Else, I is fake.
———————————-
*If ABCD and EFGH are not equal, then the fake is one of ABCD or EFGH. At this point, we know whether ABCD is heavier or lighter than EFGH.
->Suppose ABCD is heavier than EFGH.
Step 2: Compare {AB(possibly heavy fake)+E(possibly light fake)+I(definitely not fake)} and {CD(possibly heavy fake)+F(possibly light fake)+J(definitely not fake)}.
–>If AB+E+I is lighter than CD+F+J, then E or C or D is fake.
Step 3: compare C with D.
If they are equal, E is fake.
If C is heavier than D, C is fake.
Else, D is fake.
–>If AB+E+I is heavier than CD+F+J, then A or B or F is fake.
Step 3: compare A with B.
If they are equal, F is fake.
If A is heavier than B, A is fake.
Else, B is fake.
–>If AB+E+I is equal to CD+F+J, then G or H is fake.
Step 3: compare G with I.
If they are equal, H is fake.
Else, G is fake.
->Suppose ABCD is lighter than EFGH. The reasoning is similar to the case when ABCD is heavier than EFGH (replace A with E, B with F, C with G, D with H and proceed accordingly).
—————————————-
But I have better solution for the first case, where ABCDEFGH are equal. (Step 1)
We know that IJKL has 1 fake coin, not knowing it’s heavier or lighter.
Step 2:
So, take I aside; and compare JKL with either 3 coins from ABCDEFGH.
If JKL is heavier, we know that one of them is fake and the fake is heavier.
Step 3:
Compare K & L, if they are equal; J must be fake.
If K is heavier, then K is fake.
The same principal apply if the fake is lighter.
If JKL is equal with either 3 of ABCDEFGH, then the fake is I.
But we still have 1 more chance to find out the fake is heavier or lighter, so just compare I with any of those coins and you know the result.
Using this method, combine with my friend method, we managed to find out the fake coins in 3 weighing steps, and know if the fake is heavier or lighter.
I think we’ve covered all possible cases. Did I miss anything?