Question: You are give 12 identical looking balls. One of them is fake (could be heavier or lighter) than the rest of the 11 (all the others weight exactly the same). You a provided with a simple mechanical balance and you are restricted to only 3 uses. Find the fake ball.
Answer: For convenience sake, let’s name the balls 1-12. This question is quite tricky. If you want to warm up your skills, you can try this easier 8 ball problem first.
Ok, let’s get on with it.
First we weigh {1,2,3,4} on the left and {5,6,7,8} on the right. There are three scenarios which can arise from this.
If they balance, then we know 9, 10, 11 or 12 is fake. Weigh {8, 9} and {10, 11} (Note: 8 is surely not fake)
If they balance, we know 12 is the fake one. Just weigh it with any other ball and figure out if it is lighter or heavier.
If {8, 9} is heavier, then either 9 is heavy or 10 is light or 11 is light. Weigh {10} and {11}. If they balance, 9 is fake (heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {8, 9} is lighter, then either 9 is light or 10 is heavy or 11 is heavy. Weigh {10} and {11}. If they balance, 9 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
Phwww, that was confusing enough but we are not done yet.
If {1,2,3,4} is heavier, we know either one of {1,2,3,4} heavier or one of {5,6,7,8} is lighter but it is guarantees that {9,10,11,12} are not fake. This is where it gets really tricky, watch carefully. Weigh {1,2,5} and {3,6,9} (Note: 9 is surely not fake).
If they balance, then either 4 is heavy or 7 is light or 8 is light. Following the last step from the previous case, we weigh {7} and {8}. If they balance, 4 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {1,2,5} is heavier, then either 1 is heavy or 2 is heavy or 6 is light. Weigh {1} and {2}. If they balance, 6 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {3,6,9} is heavier, then either 3 is heavy or 5 is light. Weigh {5} and {9}. They won’t balance. If {5} is lighter, 5 is fake (lighter). If they balance, 3 is fake (heavier).
If {5,6,7,8} is heavier, it is the same situation as if {1,2,3,4} was heavier. Just perform the same steps using 5,6,7 and 8. Unless maybe you are too lazy to try and reprocess the steps, then you continue reading the solution. Weigh {5,6,1} and {7,2,9} (Note: 9 is surely not fake).
If they balance, then either 8 is heavy or 3 is light or 4 is light. Following the last step from the previous case, we weigh {3} and {4}. If they balance, 8 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {5,6,1} is heavier, then either 5 is heavy or 6 is heavy or 2 is light. Weigh {5} and {6}. If they balance, 2 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {7,2,9} is heavier, then either 7 is heavy or 1 is light. Weigh {1} and {9}. If they balance, 7 is fake (heavier). If they don’t balance then 1 is fake (lighter).
Voila!!!!
Head is spinning yet. Take out a paper and try it out just to get things clear. Now that you know how to solve this problem, you are ready to take on this world.
If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
Let’s make it really simple. There is no need to decide what the second and third weighings will be based on the first (or first and second) weighings.
Label your 12 balls with the letters “THE KP FORMULA”
Weigh:
TAKE against FOUR
Weigh:
PARK against THEM
Weigh:
HALF against MORE
Tabulate your results, and you will find that for any set of three results, there is only one ball which can be the fake (and whether it is heavier or lighter) which will give you the observed results.
We have three weighings, each of which can give 3 possible results: Right pan goes down, Left pan goes down:, Pans balance.
This gives us 3*3*3 possibilities (27 results)
We only need to identify 24 possibilities, (one of 12 balls is lighter/heavier than the others).
GooD work
In your first step part B, if 1-9 is lighter, you cant say fake ball is in 1-9 because you don’t know if the fake ball is lighter or heavier. Not knowing if the ball is heavier or light is what makes this question tougher.
For the 12 Identical Balls Problem,
using the same method, the maximum number of balls can be up to 27.
First step: 1-9 weight with 10-18,
A. balance ==> fake ball in 19-27.
B. 1-9 lighter ==> fake ball in 1-9.
C. 1-9 heavier ==> fake ball in 10-18.
Second step: take the group of nine balls (A is 19-27, B is 1-9, C is 10-18)
weight the first six balls with three on each side.
a. balance –> fake ball in the leftover 3.
b. imbalance –> fake ball in the lighter group of 3.
Third step: take any two of the three and weight one on each side.
I) balance –> the leftover one is the fake ball.
II) imbalance –> the lighter one is the fake.
New
|
Reply
Reply all
Forward
|
Delete
Mark as ▼
Move to ▼
|
Print
[Refresh]
{9,10} compare with {11,12}. if both are equal then the problem reduces to 8 ball problem which can be done in 2-balances.
How about dividing {1,2,3,4,5} ,{6,7,8,9,10},{11,12}
if ur lucky u get in 2 uses else 3
lets split them into 4 grps of 3 each..A(1,2,3) B(4,5,6) C(7,8,9) D(10,11,12)…then weigh A against B and C vs D..So now in 2 tries we can find out which grp has the ball with the diffe weight..then in another 1 try we can find out the different ball…correct me if am wrong guys….
Ahaaa… You are absolutely right about that. I corrected the solution now. 🙂
Thanks
Under :If {1,2,3,4} is heavier,
If {3,6,9} is heavier, then either 3 is heavy or 5 is light or 6 is light. Weigh {5} and {6}. If they balance, 3 is fake (heavier). If they don’t balance then whichever one is lighter is fake (lighter).
Only possibilities are Either 3 is heavier or 5 is lighter. 6 can’t be lighter as {3,6,9} is heavier.
I’m sorry, but there is a slight inconsistency in the subcase where {1,2,3,4} is heavier, and then after weighing {1,2,5} with {3,6,9} the latter turns out to be heavier. The answer states that in that case, either “3 is heavy or 5 is light or 6 is light”. The first two possibilities are correct, but 6 cannot possibly be light, since {3,6,9} would not be heavier then. Therefore, it can only be that either 3 is heavy or 5 is light, which simplifies this subcase a little bit. One should then take any ball other than 3 and weigh it against 5 — if they balance out, then 3 is fake (heavier), and if not then 5 is fake (lighter).
Similarly, in the very last subcase where {5,6,7,8} is heavier and then {7,2,9} is heavier, it is impossible for 2 to be light, as is currently mentioned in the answer. Either 7 is heavy or 1 is light.
Hi Sbudah, your solution will work if we knew that the fake ball was heavier but we don’t. The fake ball could be heavier or lighter. We do not know that.
What about weighing {1,2,3,4,5,6} against {7,8,9,10,11,12}. If either is heavier we take the lighter side off the scales and bring in 3 from the heavier side e.g. 1-6 was lighter so we remove it and replace it with {7,8,9} and weigh them against {10,11,12}.
Again, the heavier side remains. We remove two balls from the heavier side and place only one of them on the other side of the scale e.g. 10 against 11. If they balance, then it is the one that was not on the scale — in this case it’s 12. If one is heavier then it is the fake ball.