Even-steven
Twelve iron canon balls have the same weight, but for one that has a different weight. Find the odd ball, using only three weighings on a balance scale and determine whether it is light or heavy.
posted by littlecow at 1/13/2006 10:11:00 AM
5 Comments:
This comment has been removed by a blog administrator.
I just posted and deleted the previous post, because it had some extraneous stuff.
Anyhoo, let the balls be divided into 4 groups - A(1,2,3), B(4,5,6), C(7,8,9) and D(10,11,12).
1) Weigh A against B. If they are equal, then unequal ball is in C or D.
2) Weigh A vs C. If A and B are equal and A and C are equal, then D has the unequal ball.
If A and C are not equal, C has the unequal ball.
If A and B are not equal, then also weigh A and C. If they are equal, then B has the unequal ball, otherwise A has
the unequal ball.
3) We know which triplet has the unequal ball.
a) If A has the unequal ball. This means A and C are unequal. So we know whether A is heeavier or lighter than C.
So weight 1 against 2. If they are equal, then 3 is the unequal ball,. otherwise we know which of 1 and 2 is the
unequal ball.
b) B has the unequal ball. We know if B is heavier or lighter than A. So just like in 3a, we can identify the
unequal ball and whether it is lighter or heavier.
c) If C has the unequal ball, then we know if it lighter or heavier than A from weighing 2. So like in 3a and 3b,
we can identify the unequal ball and whether it is lighter or heavier.
d) This is a problem. Weighing 1 and 2 have produced equal results i.e A=b and A=C. So we know D has the unequal
ball, but don't if it has to be lighter or heavier. So we can't identify both the unequal ball and whether it is
heavier or lighter than the rest. We can do one or the other.
Break it up in to 2 equal halves of 6 balls - A and B and weigh them against each other.
If A was heavier, split it up into 2 equal halves of 3 balls each - A1 and A2 and weigh them against each other.
If A1 was heavier, split it into 3 piles of 1 ball each. Take 2 of them and weigh them against each other. IF both are found to be of equal weight, then the 3rd ball is heavier. If one of them is heavier, then that is the heavier ball,
Thank you to all who tried. Niranjan knew the solution to this problem from his coding theory class and abstained from providing the solution - Honesty appreciated.
@raju: Your solution follows the standard approach, the idea being to start with the assumption that a ball is heavy=> the last step would have 3 balls. weigh one against the other and three cases arise. for each of the cases, the heavier ball can be identified uniquely. backtrack and you will come up with the division into 4 groups. But, the basic assumption in step 1 cannot be made. And thats why your solution won't work.
@b-a-l: We dont know if the ball is heavier or not.
@grenade: Congratulations! Done like a jumbangwa! :-D
@all: Grenade's solution is correct and is quite clear. If you work through it, you will realize that it works perfectly well!
This is another solution Ganesh (a colleague of mine) and I came up with before seeing Jumba's:
Proceeds according to Jumba's solution for the first few steps:
Divide into 3 groups of 4 each. If the first weighing of 4 balls on either side produces an equal result, the solution is the same as Jumba's. i.e. take 3 equal ones and weigh against 3 of the ones that were not weighed etc.
If the first weghing is unequal, the balls are LLLL, HHHH and EEEE after the first weighing, with the terminology such that the lighter ball is in the LLLL group or the heavier ball is in the HHHH group, without loss of generality.
Second weghing would be such that you choose 6 balls, 3 on each side:
LLH vs LEH (the remaining group of unknown balls is HHL)
case 1: LLH > LEH means the balls are now limited to the H or the L.
case 2: LLH < LEH means the balls are now limited to LL or the H.
case 3: LLH = LEH, meaning the balls are now limited to HHL
In each case, the last weighing is now limited to 3 balls or lesser, and it is known whether the balls could be lighter or heavier and the weighing split is trivial.
Post a Comment
<< Home