Problem :
You are given 8 identical looking balls. One of them is heavier than the rest of the 7 (all the others weigh exactly the same). You a provided with a simple mechanical balance and you are restricted to only 2 uses. Find the heavier ball.Solution :
For convenience sake, let’s name the balls 1-8.Step 1 : First we weigh {1,2,3} on the left and {4,5,6} on the right. There are three scenarios which can arise from this.
Scenario 1 / Step 2
If the left side is heavier, then we know that one of 1, 2 or 3 is the heavier ball. Weigh {1} on the left and {2} on the right. By doing this, we will know if 1 or 2 is heavier. If they balance out, then 3 is the heavier one.
Scenario 2 / Step 2
If the right side is heavier, then we know that either 4, 5 or 6 is the heavier ball. Weigh {4} on the left and {5} on the right. By doing this we will know if 4 or 5 is heavier. If they balance out, then 6 is the heavier one.
Scenario 3 / Step 2
If {1,2,3} and {4,5,6} balance out, then we know either 7 or 8 is the heavier one. Weigh both of them to find out which one is heavier.
So we got the solution in 2 steps.
Another solution which I saw at career cup was also good one. See here.
We can find the different one in 3 comparations by following steps:
Divide these 8 coins into 4 groups
group[1] = [1,2]
group[2] = [3,4]
group[3] = [5,6]
group[4] = [7,8]
then
COMPARE group[1] with group[2] if group[1] has the same weight with group[2] //now we know [1,2,3,4] are good COMPARE group[1] with group[3] if group[1] has the same weight with group[3] //now we know [1,2,3,4,5,6] are good COMPARE 1 with 7 if 1 has same weight with 7, then 8 is fake else 7 is fake else //now we know the fake one is in [5,6] and whether if it's heavier or lighter!!! if group[1] is heavier than group[3]//the fake one is lighter COMPARE 6 with 7, the lighter one is fake else//the fake one is heavier COMPARE 6 with 7, the heavier one is fake else //now we know [5,6,7,8] are good if group[1] is heavier than group[2] COMPARE group[1] with group[3] if group[1] has the same weight with group[3] //now we know the fake one is in [3,4] and the fake one is lighter COMPARE 3 with 4, the lighter is fake else//now we know the fake one is in [1,2] and the fake one is heavier COMPARE 1 with 2, the heavier is fake else COMPARE group[1] with group[3] if group[1] has the same weight with group[3] //now we know the fake one is in [3,4] and the fake one is heavier COMPARE 3 with 4, the heavier is fake else//now we know the fake one is in [1,2] and the fake one is lighter COMPARE 1 with 2, the lighter is fake
Thanks
0 comments:
Post a Comment