Re: Interview Question-- Marble puzzle

Rona Crystal <r#as#crystal_at_d#as#ri.mc#as#graw-hill.com> wrote in article <5o6koi$r1s_at_mgh_cs1.mgh.com>...
> In article <FscdMLASQZozEwmG_at_jbdr.demon.co.uk>, Jeremy_at_jbdr.demon.co.uk
> says...
> >
> >In article <33A06770.161E_at_aig.vialink.com>, Johnny Barnes
> ><jbarnes_at_aig.vialink.com> writes
> >>Last summer I interviewed with a large airline firm for a dba position
> >>and the first technical question asked was - If you have 8 marbles all
> >>of the same size but one is heavier how can you find the heavy marble
> >>with a set of balance scales in just 2 weighings?
> >
> >Well clearly you'd need 3, so I guess this must be a lateral thinking
> >test - probably involving some highly debatable "trick".
> >
> >What was the answer and did you get it correct?
> >
> >--
> >Jeremy Rickard
>
>
> No trick here, just have to look beyond the obvious, but I'm not sure
 that I
> could have come up with the answer under pressure of an interview.
>
> Divide the marbles into three groups of 3, 3, and 2. Put both groups of
 3
> on the scale (weighing #1). If they balance the heavy one is in the 2
 group
> and you put each of those on the scale (weighing #2) and you have found
 it.
> If the two groups (in weighing #1) of 3 do not balance, you know with
 group
> has the heavy one so weigh (alternate weighing #2) any two of them and
 you
> now know which one of them it is.
>
> While skills like this may come in handy in identifying and solving
> problems, I'm not sure the lack of the correct answer is meaningful. The
 

> first time I read the question in the original post, I thought about it
 but
> couldn't get the answer. When I saw it repeated in this post, the answer
 

> just popped into my mind. So, so I guess that I would have missed it on
 the
> interview.
> --
> =====================================================================
> Note: My email address has been modified to discourage unsolicited
> commercial and offensive email that is sent by bulk mailers. To
> respond personally to this post, remove all strings beginning and
> ending with #. i.e. j#xx#doe_at_my#yy#comp.com becomes jdoe_at_mycomp.com
> ---------------------------------------------------------------------
> All opinions expressed here are mine alone and do not reflect
> the opinion of any other individual or organization.
> =====================================================================
>
>

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 Sun Jun 22 1997 - 00:00:00 CDT