Maxim Katcharov

Ranch Hand

Posts: 113

posted 13 years ago

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?

How do you find the false coin?

Arjun Shastry

Ranch Hand

Posts: 1906

1

posted 13 years ago

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 ]

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 ]

MH

Nick George

Ranch Hand

Posts: 815

Maxim Katcharov

Ranch Hand

Posts: 113

posted 13 years ago

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.

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

Ranch Hand

Posts: 1906

1

shankar vembu

Ranch Hand

Posts: 309

posted 13 years ago

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

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

Ranch Hand

Posts: 1906

1

posted 13 years ago

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 ]

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 ]

MH

Vijay Vaddem

Ranch Hand

Posts: 243

Maxim Katcharov

Ranch Hand

Posts: 113

posted 13 years ago

Vijay, please share.

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.

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

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

Ranch Hand

Posts: 243

posted 13 years ago

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

(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

Ranch Hand

Posts: 113

Vijay Vaddem

Ranch Hand

Posts: 243

posted 13 years ago

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

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

blacksmith

Ranch Hand

Ranch Hand

Posts: 1332

2

posted 13 years ago

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!

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

Ranch Hand

Posts: 113

Arjun Shastry

Ranch Hand

Posts: 1906

1

posted 13 years ago

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.

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.

MH

Maxim Katcharov

Ranch Hand

Posts: 113

posted 13 years ago

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:

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

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 ]

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:

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

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

Ranch Hand

Posts: 820

posted 13 years ago

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.