Solution for 12 Ball Problem
NOTE : N represents a normal ball
Name the 12 balls as A1,A2,A3,A4,B1,B2,B3,B4 C1,C2,C3 and C4.We will weigh A's on one side and B's on the other side.
A1 A2 A3 A4 <---> B1 B2 B3 B4
If Both weighed same then the odd ball is among C's.
We have to find the odd ball among 4 balls using 2 weightings.For that we balance
C1 C2 with C3 N.
Now if C1 C2 equals C3 N then C4 is the odd one.
Now suppose C1 C2 is heavier than C3 N then we compare
C1 C3 to N N
Now if C1 C3 equals to N N the C2 is the odd ball.
If C1 C3 is lighter than N N, then C3 is the odd ball.
If C1 C3 is heavier than N N then C1 is the odd ball.
Coming to the situation where the first weighing resulted in unequal balance.Lets assume A's are heavier than B's.
ie .
A1 A2 A3 A4 > B1 B2 B3 B4
Now we compare
A1 A2 B1 B2 to N N N B4.
if A1 A2 B1 B2 > N N N B4
The odd ball is among A1 A2 or B4 and we also know that A1 A2 > B4 N.To find out the odd ball among A1 A2 and B4 we do compare
A1 B4 to N N .
if A1 B4 > N N then
A1 is the odd ball
if A1 B4 < b4 =" N" b2 =" N"> N B3 which we have already shown how to solve.
Solution for 13 ball problem is easy if we could solve 12 ball problem.For that lets assume we have an extra ball C5.Now if A's and B's dont weigh same we have all the steps already calculated.
Now if A's and B's weigh same then the odd one is among C's.
Now we compare
C1 C2 to C3 N.
If C1 C2 = C3 N then we can find out the odd ball from C4 and C5 by comparing it with any normal ball.
Else if C1 C2 > C3 N then we compare
C1 C3 to N N.
If C1 C3 > N N then C1 is the odd ball
If C1 C3 = N N then C2 is the odd ball
If C1 C3 < N N then C3 is the odd ball
Subscribe to:
Post Comments (Atom)
18 comments:
Isn't this the solution to the 12 balls problem? you only have C1-4. Also you have a type-o, you meant to say B4 is the oddball for the A1B4 < NN comparison, not A4.
SPOILER -
I wondered about that too, Mike, but then noticed that the 12 ball version got to a unique solution within 2 comparisons in the case that A1-C3 are all in the N set.
So (assuming the rest of the math is good) to fix this for 13 balls, you only need to check whether the odd one is C4 or the thirteenth ball (D1) by either C4 vs N or D1 vs N.
I still have the same question.
How in the name of all that is holy are you supposed to know this stuff without being given examples before hand? I am assuming that you either have to be really smart or you're just out of luck. Am I right?
I believe this solution only works for the 12 ball problem. If you separate 13 balls into 8 and 5 as you do for your first weighing, you wind up with the possibility of finding the odd ball among 5, which I believe requires 3 more weighings. If someone can post how to solve 5 in 2 steps, please do.
See my solution on the puzzle thread
Steve - You neglected the case where C1C2 > D1A1.
See scenario 2 for my solution to the puzzle regarding how to solve 5 unknowns in 2 steps.
Remember that we do not need to know if the odd ball is heavier or lighter, only that it is the odd one.
I have updated the solution with 13 balls solution also
Alisa had the solution yesterday. It is the same as my method, and elegantly explained, so I didn't post mine. At the start, it does not assume the odd ball is heavy or light. This solution is better than the "official" solution given today, since at the end, you know which is odd and if the defect is heavy or light for all cases.
J, also this solution solves the remaining 5 ball case in two weighings.
Alisa, you are hired!
Alisa's solution is a fine one, and neatly explained, but Gearspring is wrong... None of the solutions explain the defect in all cases (Alisa's fails to tell whether c5 is heavier or lighter). I don't think this would be possible.
My preferred explanation was that of the first Steve (not the same as the above, which didn't work). Mine was the same as Mike's (I haven't examined the official one, sorry if it's the same):
1. Try [ABCD v EFGH]
1= => Try [IJ v KH]
2= => L? or M?, try [L v H]
2< => I- or J- or K+, try [I v J]
2> => I+ or J+ or K-, try [I v J]
1< => Try [ABEF v GKLM]
2= => C- or D- or H+, try [C v D]
2< => A- or B- or G+ try [A v B]
2> => E+ or F+, try [E v F]
1> => specular to 1<
If you find any error, please tell.
When I solved the 12 ball question, the answer I got actually led itself to an even trickier question. So try this one on for size:
You have 12 balls, 3 weighings. They are all the same weight, except one may or may not be different. If it is different it may be heavier or lighter. You must tell me if one is different, and if so, heavier or lighter.
Oh and by the way, you can not change your logic based on the outcomes. You're going to tell me "Weigh set A vs. set B, set C vs. set D, and set E vs. set F", I'll come back and tell you "A was heavy, D was heavy and E and F were balanced"
hi we will divide the balls in the set of 5,5,2
Hi,see my solution on my blog of Feb 8
http://darkeyesmaddermadder.spaces.live.com/
I also posted some other microsoft interview questions and solutions there.
This solution couldn't find whether the odd ball is a lighter or a heavier ball in three weighings!?
dear friends,
i dont know the solution u have suggested or not but my solution requires 4 weighings(not 3)
lets divide 13 balls in
A1A2A3A4
B1B2B3B4
C1C2C3C4C5
Weigh A1A2A3A4 vs B1B2B3B4(1at weight)
IF they are equal
A1A2A3A4 B1B2B3B4 are good balls
and C1C2C3C4C5 got the defective one
we know As are good ones
Weigh C1C2C3 vs A1A2A3(2nd weight)
IF they are equal
Weigh C4 or C5 vs A1(3rd weight)
IF C4 = A1 then C5 is defective
else C4
IF C1C2C3 vs A1A2A3 is not equal means note whether lighter or heavier(2nd weight)
C1C2C3 got the defective one as A1A2A3 are good
weigh either C1 vs C2 or C2 vs C3 or C1 vs C3(3rd weight)
we have noted ealier if C1C2C3 is lighter side then it contain a lighter defective ball else vice versa.
Assume C1C2C3 is heavier n C1 vs C2
IF they r equal then defective is C3 else The heavier among C1 n C2
IF A1A2A3A4 != B1B2B3B4(1st Weight)
Note the Lighter n heavier side
C1C2C3C4C5 balls are Good
Weigh A1A2A3A4 vs C1C2C3C4(2nd weight)
If it is equal defective is in Bs
else if not equal defective is in As
Note lighter or Heavier
Weigh A1A2 vs A3A4(3rd weight)
we know it is lighter or heavier and accordingly can find out
Weigh A1 vs A2 or A3 vs A4 as per requirement(4th weight)
Similar method is to be used with Bs if it has got defective ball
I hope my answer will help all if i have done any mistake inform me.
try this even more challenging problem:
13 balls, with one odd. Use balance with 3 weighting to find our the odd AND whether it is lighter or heavier.
I enjoyed the 13 ball problem. If the odd ball is C4 or C5 you cannot determine if it is lighter or heavier in all cases. This is a little unsatisfying.
What do you think the potential employer would do if we bent the rules for a different solution?
In your first weighing you intend to weigh 6 vs 6. If these are equal the ball left is odd. Swapping the odd ball for one on the balance will tell you its relative weight.
You begin your first weighing by placing 1 ball on each side of the balance. As you reach for the second 2 balls you look at the balance. As long as the balance is even you continue to add pairs of balls. If the balance becomes uneven, you stop. One of the last 2balls is the odd ball. You swap one of the last 2 balls with an N ball. Based on the previous tilt of the balance and its behavior when the N ball is placed you know which of the last 2 balls is odd and its relative weight. This method takes less work, provides more information, and requires that only 1 ball be removed from the balance for the entire operation.
In case of 13 balls, it is not possible in 3 weighings to find odd ball with its nature ( heavier or lighter in all cases ).
If you are taking chances, then 2 weighings are enough.
But to consider all worst cases, 4 weighings are must.
Post a Comment