Re: Interview Question-- Marble puzzle

[12 marble question, with 1 lighter _OR_ heavier]

You divide the marbles into 3 groups of 4. Lets call the groups a, b and c.

Weight any 2 groups on the balance beam. For this example, we'll use a & b.

1. If they balance, then the odd marble is in group c.

It's trivial from here. Measure any 2 marbles in group c. If they balance, the 3rd marble is the one. If they don't, remove one marble from the balance and replace it with the 3rd marble. If nothing changes, the marble you did not replace is the odd one (has to be since the balance didn't change). On the other hand, if the balance is now the same, the one you removed is the odd one. You even know if the odd marble is heavier or lighter.

2. If they don't balance, you know it's in group a or b (talk about an obvious statement).

Replace the marbles on one side with the c marbles. Assume we're replacing the a's.

1. If the balance is still off, we know it's the b marbles and also whether the marble is heavier of lighter (we know because the balance didn't change). Simply measure any 2 of the b's to find the odd marble. We can do this in 1 measurement since we know whether it's heavier of lighter.
2. If the scale moves into balance, we know the a group contains the odd marble, and once again, we know if it's heavier or lighter. Again, measure any 2 of the a's to find out which is the odd marble.

The only tricky part in this problem is to find out if the marble is heavier or lighter by the second weighing.

In article <01bc7f3b$e594e630$2d9433cf_at_wilson>, "Wilson Zhang" <wzhang_at_kbg.com> says:
>

 [snip]
>I believe this question is a simplified version of one question my
>professor gave me one time.
>The question is : You have 12 metal balls. They have the exact same
>appeareance. But one ball is of different weight than all others.(Don't
>know if it's heavier or lighter.)
>You have a balanace scale. How do you identify the odd ball within 3
>tries, ie, using the scale three times?
>I came up several answers and one of them is : Divide them into 5,5,2.
> First try: compare 2 5s. If they are of the same weight, then the odd
>ball is among the remaining two. Secend try: Leave any two from one group
>of 5, put the 2 on the scale. If the new 2 is lighter, then use the last
>try to find the lighter ball among the two. If the new 2 is heavier, then
>use the last try to find the heavier one.
> It gets trickier if the 5s are not of the same weight and if that's the
>case, three tries is not enough.
> You can also get an answer to it by dividing them into 3,3,4. But no
>matter how you divide them, you don't have a guranteed solution. You will
>reach the solution if certain conditions are met,like the two 5s are of the
>same weight.
> I haven't found the complete solution yet and I tend to think it's
>NP-incomplete.
> If anyone out there knows the complete solution, ie, a solution that
>guarantees the result no matter what, please let me know.
>
>Wilson
>
Received on Mon Jun 23 1997 - 00:00:00 CDT