Hi,
I don't know if I'd call this a math problem, but of all the forum sections I figured this one is closest to the type of question I'm posting...
Anyways I was working on this logic problem:
Quote:You have 12 balls. All of them are identical except one, which is either heavier or lighter than the rest - it is either hollow while the rest are solid, or solid while the rest are hollow. You have a simple two-armed scale, and are permitted three weighings. Can you identify the odd ball, and determine whether it is hollow or solid.
I can do it easily in 4 steps, and came pretty close to doing it in 3 but not quite...
So I cheated and looked at the solution:
Quote:Let the balls be numbered 1 to 12. Firstly, put 1-4 on one side and 5-8 on other side. If both are equal then one of 9-12 is odd. Then second try, weigh 9-10 vs 1-2, if equal, one of 11-12 is bad, else 9-10 is bad. Testing which one is bad can be done by (third try) weighing 11 or 9, respectively, with good ball 1. It also gives whether the odd ball is heavy or light.
I don't get how this is a correct solution though. They seem to be assuming that 1-4 and 5-8 are equal. But if 1-4 and 5-8 aren't equal, then basically all you've done is narrowed it down to 8 balls, and afaik there's no way you can narrow it down to 1 ball in 2 remaining turns.
Anyone got any idea about this?
Thanks
roos
I think that it goes both ways. That if eitehr 1-4 is uneven or 5-8 is uneven, then any balls 9-12 should not be odd. So just replace based on scenario.
I don't understand what the AP just said. I agree with the OP that the solution is not complete, however, and I can't see a solution in 3 in the first minute of staring at it, but I'm going to keep trying :)
The common mistake with this problem (which I've seen before) is to think of a weighing as a binary operation -- with two possible results, that the left is heavier or the right is heavier. This would allow each weighing to cut the space of possible answers (commonly referred to as our search space) in half, meaning you'd need the ceiling of log-base-2 of 12 = 4 weighings to get your answer.
In truth, however, each weighing is a trinary operation -- it cuts the search space in thirds. This may not make sense at first, but it does when you consider that you don't have to put everything on the scale. If you put one-third of the remaining possibilities on one side, and another third on the other side, with the remaining third off to the side, we recognize three possible results -- that one side is heavier, or the other, or that they're the same. This possibility that they're the same would indicate that our answer lies somewhere in the group that we had off to the side. Theoretically, since we have a trinary operation to cut our search space in thirds, we may be able to do this at best with ceiling of log-base-3 of 12 = 3.
- Hai, watashi no chichi no kuruma ga oishikatta desu!...or, in other words, "Yes, my dad's car was delicious!"
I disagree... if we knew that the odd ball was heavier, yes, but we don't, so the most likely case is that we are left with 8 balls, of which either 1 of 4 is lighter or 1 of the other 4 is heavier, but we still don't know which, so our solution space is 8, not 4, and as far as I can tell, the extra bit of information we have isn't useful enough to cut the search down to 3 tries.
As a fan of lateral thinking, however, and as we are only limited in our number of weighings, I recommend striking each ball in turn with the weighing scale, and the one which sounds different is the odd one out ;)
BucketHead, I see what you are saying, and I am guessing that you're right and I'm just not seeing it fully.
The part which is tripping me up is... it doesn't always narrow your search space to 1/3 of what it was. Like, say you have 9 balls, so you split into groups A, B, and C where each group has 3 balls. Now you weigh A vs. B, and find that A is heavier. Now all you have done is ruled out the possibility of C containing the odd ball, but it's still not clear whether A has it or B has it, because you don't know if it's hollow or solid.
To put it another way, although we have a tertiary operation, we have a solution space of 24 : 12 possible heavy balls and 12 possible light balls. The only reason I'm not prepared to say for sure that this can't be done is that this "space" is 2-dimensional ... it is 12 x 2 ... (oooh, sorry to the mathematicians - I'm not atall formal ;) and there might be a super clever way to divide it up in both directions at once.
Finally, in the original "solution", even if the first division goes in the way desired, the last bit still doesn't work... 3 measures are performed, and it is possible for all 3 to be equal, in which case we know which ball is bad (it's ball 12), but not whether it is heavier or lighter, since it has never actually been placed on a scale.
OK... I cheated some more (hehe) and found an answer to it... Actually the original solution is correct (nothing it said was wrong), it just isn't complete because it didn't show what to do if the first weighing is unbalanced.
This is a pretty tough problem I think... you got to choose the first 2 steps carefully (not so much the 3rd because by that point the answer becomes obvious), and you also have to realize which balls you should move around in the 2nd step
That first test gives no indictation on weather the odd ball is in 1-4 or 5-8 it only tells you if it's 9-12 or not.
My solution.
if 1-2 != 3-4 if 1 != 2 // 1 or 2 is odd? return 1 != 3 ? 1 : 2; else // 3 or 4 is odd! return 3 != 1 ? 3 : 4; else if 5-6 != 7-8 //repeat the same thingelse if 9-10 != 11-12 //repeat the same thing
