False Coin

[Maxim Katcharov]

You have a set of 12 coins. It has come to your attention that one of the coins is false - heavier or lighter, but otherwise identical. Your friend offers you the use of a scale, but you better be quick about it, he needs it back real soon or the museum will notice that it's missing. You have just enough time to weigh any amount of coins against any other amount three times.

How do you find the false coin?

[Arjun Shastry]

What a "coin"cidence!I was doing a same problem before logged on to net and read the problem.!
I think this has been solved here earlier IAMNW.
12 coins we will name them as abcdefghijkl
1)put abcd on one side and efgh on other side.
2)if they weigh equal,counterfeit coin is in ijkl
3)Compare ij with ab
4)if they weigh equal,counterfeit coin is between k and l
5)compare k with any coin.If same ,l is counterfeit.
6)If abcd weighs more(or another way),replace cd with ef and ef with cd and gh with ij(or kl)
7)If abef weighs more again,counterfeit is between a and b.
8)If abef weighs less,counterfeit is between c and d.
9)If abef weighs same as cdkl,counterfeit is between g and h.

Then depending on outcome compare any one coin with authentic one.
3 weighings will be required.
[ September 18, 2004: Message edited by: Arjun Shastry ]

[Nick George]

IAMNW?

[Maxim Katcharov]

so if abcd = efgh, F is within ijkl, and it's simple from there, otherwise try for:

abcd > efgh
abef vs cdTT

>7)If abef weighs more again,counterfeit is between a and b.
>8)If abef weighs less,counterfeit is between c and d.
>9)If abef weighs same as cdkl,counterfeit is between g and h.

I've heard that there are a number of distinct ways to do this. This is the second I've seen.

[Arjun Shastry]

If there are N coins,how many minimum weighings to find false coin?

Originally posted by Joseph George:
IAMNW?

I forgot one additional I.So its (If I AM Not Wrong)!!
[ September 22, 2004: Message edited by: Arjun Shastry ]

[shankar vembu]

Originally posted by Maxim Katcharov:
so if abcd = efgh, F is within ijkl, and it's simple from there, otherwise try for:

abcd > efgh
abef vs cdTT

>7)If abef weighs more again,counterfeit is between a and b.
>8)If abef weighs less,counterfeit is between c and d.
>9)If abef weighs same as cdkl,counterfeit is between g and h.

I've heard that there are a number of distinct ways to do this. This is the second I've seen.

Are you assuming that the counterfeit coin is always heavier than the original one?
Assume 'e' is counterfeit and is lighter than the original coin.
1. abcd > efgh holds.
2. if abef < cdTT also holds but the counterfeit is neither c nor d

am i missing something

[Arjun Shastry]

I think I was wrong.
I think instead of changing two coins ,three coins should be changed after first weighing.That means,abce and djkl will go on second weighing.
so
1)abcd----efgh if both weigh equal,false coin is in ijkl.Compare ij with ab if they weigh equal,compare a with k.If they(ij--ab) do not weigh equal then compare i with a.
2)abcd weighs more than efgh.Exchange d and e and replace fgh with jkl(true coin).If abce again weighs more,false coin is between abc.If abce weighs less,false coin is between d and e.
Is this right? or something is missing?
[ September 22, 2004: Message edited by: Arjun Shastry ]

[Vijay Vaddem]

This was one of the interview question i had recently..... and i
answered it correctly...!!!

[Maxim Katcharov]

Vijay, please share.

Originally posted by shankar vembu:
am i missing something

No, I am. Damn. My life is a sham... a simple 13 year old I know solves this, and I cant even pick out a flaw in a possible solution.

2)abcd weighs more than efgh.Exchange d and e and replace fgh with jkl(true coin).If abce again weighs more,false coin is between abc.If abce weighs less,false coin is between d and e.
Is this right? or something is missing?

You didn't state any results with the false coin being amidst fgh. If it doesn't work, you're about one step of logic away from the solution I got...

[Vijay Vaddem]

Ok.....let me rephrase the above question with another example...
(my interview question)

----------------------
Question:
----------------------

You have 8 similar balls. Out of these 8 balls, 1 ball is lighter than
the other 7 balls where all the 7 balls are equal in weight.

You have 2 chances to weight the ball and find out which ball is the lighter
one....

-------------
Solution....
-------------

1. Take any 6 balls....
2. weigh them....
3. If they are equal.... the odd one is one among the remaining two balls, measure those two balls and find the lighter one.
4. If they are not equal, take the 3 balls from the pan which is lighter in weight.
5. Take 2 balls from these 3 balls and measure them, if they are equal
the remaining one is the lighter one(the odd one). Otherwise,
one among those 2 balls would be the odd one.....

Hope im clear in this.... and i feel the same solution may be
applied to the above problem by taking 8 coins at a time and following
the same steps above.

Cheers...

[Maxim Katcharov]

I see no flaws, though the situation is reversed between the two problems... with the 8 balls, you know if the ball is heavy/light, but not which group is heavy/light. With the 8 coins, you know which group is heavy/light, but not if the ball is heavy/light.

[Vijay Vaddem]

When we weight the 6 balls, we put 3 balls each in the pans......

Lets say balls :ABC into one pane
and balls : DEF into the other...

Since, the weights are assumed to be equal for all the balls ( except one)...
the total of A+B+C = D+E+F

if the above condition is satisfied, it implies that the lighter one
should be one among G and H.

Weight them and find out the odd one.

Else, pick out the collection of 3 balls (either ABC or DEF, whichever is
lighter in total); from these three balls, pick up 2 balls
and measure the weight. U should get the odd one....

Correct me if im wrong in the solution or in understanding the
question itself ...

[Warren Dew]

The original 12 coin problem is still open, since we only had eight balls, right?

My analysis:

First, can we even theoretically figure this out? There are 24 possible outcomes: 12 possible false coins, times 2 possibilities of how the coin weighs relative to a true coin (heavier or lighter). Each weighing gives three possible outcomes, so three weighings might allow us to distinguish between 3^3 or 27 possible outcomes. We might be able to do it, but it will be close. We will need to extract the maximum amount of information out of each weighing - not just which half contains the false coin, but, if possible, information about whether the coin is heavier or lighter.

As before, label the coins abcdefghijkl.

The first weighing, as before, is abcd vs. efgh. If they are equal, the false coin is in ijkl but we don't know whether it is heavier or lighter. If abcd are lighter, the false coin is in abcdefgh and we do know whether it is heavier or lighter (lighter if abcd, heavier if efgh). (If abcd are heavier, exchange the coin labels between abcd and efgh, and follow the abcd lighter case.)

If equal, relabel the known good coins x. Now weigh xx versus ij. If different, the false coin is in ij; if the same, the false coin is in kl. Now weigh xx versus ik. If different, the false coin is in ik, if equal, it is in jl; combine this with the previous step to tell exactly which coin it is. (We also know whether it is heavier or lighter unless it is l.)

If abcd < efgh, what we'd really like to do is weigh abcefg vs xxxxxx, which would tell us whether the false coin was abc (lighter), efg (heavier), or dh (equal). Then we'd have no more than three candidate coins, and that situation could be resolved in the one remaining weighing.

Unfortunately, we only know four fair coins, not six. So we give up the information about coin c and try to get some information about coin h instead: we weigh abefg vs hxxxx.

If abefg == hxxxx, the false coin is c or d; weigh c vs x, if less, it's c, if equal, it's d.

if abefg < hxxxx, the false coin is in abh. Weigh a vs b; if equal, it's h; otherwise it's whichever of a and b weighs less.

if abefg > hxxxx, the false coin is in efg. Weigh e vs f; if equal, it's g; otherwise it's whichever of e and f weighs more.

I don't think this is a very good interview question for a software engineering position; it's too abstract. Maybe if one were interviewing a computer science PhD for an algorithms development position.

Er ... so can anyone improve on this answer to get whether l is heavier or lighter if it is the false coin? After all, if the false coin is heavier, we might want to keep it!

[Maxim Katcharov]

Originally posted by Vijay Vaddem:
Else, pick out the collection of 3 balls (either ABC or DEF, whichever is
lighter in total); from these three balls, pick up 2 balls
and measure the weight. U should get the odd one....

You dont know if the coin is heavy or light.

[Arjun Shastry]

Originally posted by Maxim Katcharov:
You didn't state any results with the false coin being amidst fgh. If it doesn't work, you're about one step of logic away from the solution I got...

if abce=djkl then false coin is in fgh.We know thatfalse coin among them is heavy or light from previous result.compare af and bg.If both weigh equal then false coin is g.If not depending upon previous result whether coin is heavy or light,we can conclude.

[Maxim Katcharov]

So:

abcd > efgh
If false is light, it would be in efgh, if heavy, in abcd.

If (abce > dTTT) then heavy within abc. d or e would weigh it in the opposite direction.
If (abce < dTTT) then de. abc would again weigh more.
If equal, then light within fgh.

I think I can safley say that's right. The solution I got was:

weighing 1:

+abcd
-efgh

...ligher in abcd, heavier in efgh.

weighing 2: abe vs cdh
If they are equal, then the lighter of f vs g.
Otherwise if abe > cdh (and this will work opposite for less than)

 +  -
+abcd
-e  h

the only ones that match are a, b under + and + "weighs more" and h under - and - "weighs less". Compare a vs b for heavier coin, equality means h is false.

I believe there're still a few ways left to solve this. I don't think it's possible to solve without weighing 4 vs 4 as the first move though...
[ September 27, 2004: Message edited by: Maxim Katcharov ]

[Joe King]

It seems that these kind of problems come up more and more in job interviews these days. I was considering studying for some kind of java certification to help my career, but instead I'll probably just get 101 Logic Problems out of the library.

[Tim Holloway]

You do realize that this is just a HeapSort in disguise, don't you?

[Maxim Katcharov]

Originally posted by Tim Holloway:
You do realize that this is just a HeapSort in disguise, don't you?

I must be looking at the heapsort thing the wrong way, I don't see it. Really curious though... mind explaining the connection?