Fog Creek Software
Discussion Board




even harder coin problem  - solution

the funda to solve it is : weigh 4 balls with other 4 at one time. and weigh each ball twice with the other three balls being entirely be different in the two weighs. Sounds confusing !!
take for example : mark the balls 1 to 12.
round 1 : weigh 1,2,3,4 Vs 5,6,7,8
round 2 : weigh 1,5,9,10 Vs 2,6,11,12
round 3 : weigh 3,7,9,11 Vs 4,8,10,12

the defective ball(whether light or heavy) can easily be found out as it will be the only common ball in the two defective groups.

Ritesh and Saurabh
Monday, May 17, 2004

Two problems in the solution posted by Ritesh and Saurabh,

1) First of all, coin prob is solved using balls :) .. kiddin !

2) Now the serious one. well just consider a simple case that the first 2 weighings result in a left tilt,it still has the ambiguity tht whether coin 1 is heavier or coin 6 is lighter......

cheers
Tuesday, May 18, 2004

I'll explain the basic approach, then give detailed instructions on how it works.

The basic approach is to weigh four against four. If they balance, then we have two more weighings to find a counterfeit in four coins, which is a relatively easy problem, since we have 8 known good coins that we can use to compare against. We weigh three of the four unknown coins against three geniune coins. From this we either determine that the counterfeit is in that group of three, and whether it is light or heavy, or we determine that it is the unknown coin that was left out. In either case, one final weighing can nail down the coin and tell us whether it's light or heavy.

The general approach for three coins when you know if it is light or heavy is to weigh one of them against another, and if they balance you know it's the one left out. If they don't, you use the coin's known weight difference to determine if it's the high or low coin on the balance.

So, the basic trick to this whole thing is, what happens in the first weighing if they don't balance? We only have two more weighings, and we don't yet know if the coin is light or heavy.

We do, however, have four coins that we now know are geniune. We will use these to help narrow the field so that we can determine the coins "lightness" or "heaviness" and reduce it to a problem of finding the coin among three that we examined above.

We keep three of the original left side there, we replace three on the right side, and we swap the remaining coin on the left and on the right.

If the scale now balances, we know that the counterfeit must be in the three we removed from the right side, and depending on how the scale originally tilted, we know if it was light or heavy.

If the scale is still inbalanced in the same direction, we know that the counterfeit is in the three originals on the left side, and we know based on the direction of the inbalance whether it is light or heavy.

In either of these cases, we can use the third weighing to find the counterfeit coin.

If the scale inbalances, but in the other direction, we know that the counterfeit must be one of the coins we swapped. We can weigh one of them against a known genuine coin to see which coin is the counterfeit, and based on the position in which the scale unbalanced, we know whether it was light or heavy.

Now I'll give a more detailed rundown on how to weigh the coins.

I'm going to give the coins letter designations to make things simpler (and so that they have the same sized representation below)
A B C D E F G H I J K L

This will be in pseudocode. Weighings are capitalized for emphasis and for easy counting/checking.

WEIGH (A,B,C,D vs E,F,G,H)
result (balanced):
    WEIGH (A,B,C vs I,J,K)
    result (balanced):
        WEIGH (A vs L)
        result (left tilt):
            counterfeit is (L: light)
        result (right tilt):
            counterfeit is (L: heavy)
    result (left tilt):
        WEIGH (I vs J)
        result (balanced):
            counterfeit is (K: light)
        result (left tilt):
            counterfeit is (J: light)
        result (right tilt):
            counterfeit is (I: light)
    result (right tilt):
        WEIGH (I vs J)
        result (balanced):
            counterfeit is (K: heavy)
        result (left tilt):
            counterfeit is (I: heavy)
        result (right tilt):
            counterfeit is (J: heavy)
result (left tilt):
    WEIGH (A,B,C,H vs I,J,K,D)
    result (balanced):
        WEIGH (E vs F)
        result (balanced):
            counterfeit is (G: light)
        result (left tilt):
            counterfeit is (F: light)
        result (right tilt):
            counterfeit is (E: light)
    result (left tilt):
        WEIGH (A vs B)
        result (balanced):
            counterfeit is (C: heavy)
        result (left tilt):
            counterfeit is (A: heavy)
        result (right tilt):
            counterfeit is (B: heavy)
    result (right tilt):
        WEIGH (A vs D):
        result (balanced):
            counterfeit is (H: light)
        result (right tilt):
            counterfeit is (D: heavy)
result (right tilt):
    WEIGH (A,B,C,H vs I,J,K,D)
    result (balanced):
        WEIGH (E vs F):
        result (balanced):
            counterfeit is (G: heavy)
        result (left tilt):
            counterfeit is (E: heavy)
        result (right tilt):
            counterfeit is (F: heavy)
    result (left tilt):
        WEIGH (A vs D):
        result (balanced):
            counterfeit is (H: heavy)
        result (left tilt):
            counterfeit is (D: light)
    result (right tilt):
        WEIGH (A vs B):
        result (balanced):
            counterfeit is (C: light)
        result (left tilt):
            counterfeit is (B: light)
        result (right tilt):
            counterfeit is (A: light)

As you can see from the counterfeit result lines, there is exactly one case for each of the 24 possibilities (light or heavy for each coin), and it is achieved in exactly three weighings for each case.

Jacob Cohen
Thursday, May 20, 2004

You're choosing what to weigh based on the results of previous weighings. This is disallowed for this problem.

Ham Fisted
Thursday, May 20, 2004

Gah, you're right, I didn't read closely enough.

Not only did my solution not solve this problem, but then I went and read the original (pill) problem and someone's already posted this solution. Sigh. What a waste of space.

Jacob Cohen
Thursday, May 20, 2004

Here's the approach I took towards this problem.
In order to come up with 12 different conclusions, we need 12 different results at the end.  Here are all the possible results for 3 weighings:
> > >
> > <
> > =
> < <

okay, I'm getting restless typing them all out :D so I'll just say that since there's 3 possibilities, and 3 weighings, there are 3 to the 3rd power results possible, for a total of 27 different results.

Out of those 27, some are mirror images of others.  For example:
> > >
is a mirror image of:
< < <
We must eliminate all the mirror images, because then we won't be able to differentiate between heavy and light coins.  When we do that, we are left with 14 possibilities:

1) > > <
2) > < >
3) > < <
4) > > =
5) > < =
6) > = >
7) > = <
8) > = =
9) = > >
10) = > <
11) = > =
12) = = >
13) > > >
14) = = =

We can't use "= = =" because that would mean we would have to avoid using one coin (ball? :)) altogether, and if that ball happens to be the different one, we'll never know whether it's heavier or lighter.  That leaves us with 13.  We also can't use "> > >" because when we assign numbers to each possibility, we won't be able to balance out the scale with "> > >" so we eliminate it as well.  That leaves us with 12 possibilities (how convenient ;))

Now, assign numbers to the different possibilities and place them on the scale.  Everytime you see two of the same symbol (ex. > >) you place them on the same side of the scale each time.  Everytime you see a different symbol (> <) you place them on opposite sides of the scale.  Whenever you see the "=" you leave that ball out of that weighing.

So.  Assigning the balls to our possible results, numbered 1-12:

1) > > < ---- 1
2) > < > ---- 2
3) > < < ---- 3
4) > > =  ---- 4
5) > < =  ---- 5
6) > = >  ---- 6
7) > = <  ---- 7
8) > = =  ---- 8
9) = > >  ---- 9
10) = > <  ---- 10
11) = > =  ---- 11
12) = = >  ---- 12

Then, organize them on the scales so that they balance out:

1, 3, 5, 8    -----------    2, 4, 6, 7

1, 2, 9, 11    -----------    3, 4, 5, 10

7, 9, 10, 12    -----------    1, 2, 3, 6


And that's it. :o)


Hope my explanation made sense. :o)


Eliza

eliza s
Monday, June 14, 2004

*  Recent Topics

*  Fog Creek Home