Re: Interview Question-- Marble puzzle

Darn, I didn't review my answer carefully enough before I sent it out before. Here's the correct answer.

Divide the marbles into 3 groups of 4. Call them A, B, and C.

Measure A against B.

If they balance, the odd marble is in group C, and the solution from there is straightforward. Measure any 2 in C. If they balance, one of the remaining C's is the one. The 1 remaining weighing will tell us which one it is. If they don't balance, remove one of the marbles from that scale, replacing it with another marble. This tells us if the marble we removed is the one, or the one remaining on the scale is the one.

The real problem is when groups A and B don't balance after the first weighing.

Here's what you do.

Take 3 marbles from B, and replace them with 3 marbles from C.

Take the 3 B marbles and put them on the A side.

We now have ABBB and BCCC on the 2 sides of the balance scale.

If the scale balances, the odd marble must be one of the 3 A's that we removed. This also tells us if it was heavier or lighter. Since we now know if it's heavier or lighter, we can measure any 2 of the 3 A marbles, if they balance the 3rd A is the one. If not, since we know whether it's lighter or heavier, we can isolate the odd marble.

If the scale doesn't balance, it must be either the A or the B that we left on the scale. Measuring either one will determine which is the odd marble.

Sorry about the incorrect response that I sent out before. That's what happens when work gets in the way. :-)

Phil

In article <5omj83$ccd$1_at_news-2.csn.net>, pxchang0_at_sunspot.wcc.com (phil chang) says:
#[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.
#
#a) 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.
#
#b) 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  
>>