Thursday, October 6, 2011

8 identical balls one being heavier

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