Problem of the Day
A new programming or logic puzzle every Mon-Fri

Comments:

• vlad - 10 years, 9 months ago

  You divide the balls in three groups of 3 balls each. You then compare two groups. If any of the groups weighs less, we know the ball is in one of them. If they weigh the same, then we know the ball is in the unweighted group. After selecting the group, we take a ball out, and weigh the remaining balls. If they weigh the same, the ball we are looking for is the one we took out, otherwise it's the one indicated by the scale.

  The second problem is solved in pretty much the same way. All we need to do is weigh once more in the beginning, between two groups of 6 balls.

  reply permalink

• heartinpiece - 10 years, 9 months ago

  The second problem can be done likewise, but I can think of two ways.

  1. Partition the balls into 4 groups of 3 balls. Compare first two groups. If one group weighs less, pick that group and compare as done in the first problem. In this case we only need to use the weight twice(best case). If the first two groups weigh the same, then weigh the third and fourth group. Then pick the group that weighs less and do that same.
  2. Partition groups into 4 balls and three groups. pick two of the groups, and weigh. If either weighs less, that is the group with the ball we want to find. Else, the unweighed group is what we are interested in. When we have the group of 4 balls, we can weigh the first two, then the last two. Again, here we could only use the weight once :)

  reply permalink

• kdak - 10 years, 9 months ago

  You've used the scale more than twice for test 1.

  reply permalink

• Carlos - 10 years, 9 months ago

  • Test 1:
  • Put 3 balls in each scale;
  • If the weight is the same, the left out group of 3 has the heaviest ball;
  • If not, pick the heaviest group of 3 balls;
  • 1 of the ball goes out the other 2 go into the balance, one on each side;
  • If the weight is the same, the left out ball is the heaviest ball;
  • If not, pick the heaviest ball on the scale;
  • Test 2:
  • Put 6 balls in each scale;
  • pick the heaviest group of 6 balls;
  • Do test 1 all over again;

  reply permalink

• Carlos - 10 years, 9 months ago

  Do test 1 all over again but instead of working with groups of 3, you work with groups of 2

  reply permalink

• gulliver - 10 years, 9 months ago

  For Test 2:
  
  
  Weigh 4 vs 4
  
  If they balance - we have narrowed it down to the 4 balls we didn't weigh and can mark the other 8 balls as NO
      Weigh 2 unknown balls vs 2 NO balls
      If they balance - then we are down to the remaining 2 balls we didn't weight
      If they don't balance - we know it is one of the 2 unknown balls we weighed
      Either way we are down to 2 balls
          Weigh 1 unknown ball vs 1 NO ball
          If they balance the odd ball is the other unknown ball
          If they don't balance the odd ball is the unknown ball we just weighed
  
  If they don't balance - we can label 4 as H and 4 as L (and the remaining 4 are NO)
      Weigh 2H + 2L vs 1H + 1L + 2 NO
      If they balance - we are down to the remaining 1H and 1L ball we didn't weigh
          Weigh 1H vs 1 NO
          If they balance then we know the odd ball is the 1L ball remaining
          If they don't balance we know that the 1H ball is the odd ball
      If they don't balance:
          If the left side is heavier we know the odd ball is either one of the 2H on the left or the 1L on the right
          If the right side is heavier we know the odd ball is either one of the 2L on the left or the 1H on the right
          Either way we have narrowed it down to 3 balls (2H 1L or 2L 1H)
          If we have 2H weigh 1H vs 1H
          If they balance then we know the odd ball is the 1L
          If they don't balance then the heavier one is the odd ball
          If we have 2L weigh 1L vs 1L
          If they balance then we know the odd ball is the 1H
          If they don't balance then the lighter one is the odd ball
  

  reply permalink

• Knight2E4 - 10 years, 9 months ago

  Test 1 is relatively easy: Divide into 3 groups of 3. Weigh group 1 and 2. If they are equal, group 3 contains the fake, otherwise take the lighter of 1 and 2. Weigh balls A and B from that group. Again, if equal, ball C is the fake, otherwise the lighter of A and B is the fake.

  Test 2 is definitely much trickier. The important piece of information is that really you only know the fake has a different weight. You will have to retest inequalities rather than selecting from a set of 3 options. This time I will label all of the balls for tracking. Divide into three groups containing four balls [A, B, C, D]; [E, F, G, H]; [I, J, K, L]. (1) Weigh [A, B, C, D] against [E, F, G, H].

  If [A, B, C, D] = [E, F, G, H]: (2) Weigh I against J. Equal, (3)weigh I against K; equal gives L is fake. I!=J weigh, I against K; equal gives J is fake. This covers I, J, K, L.

  If [A, B, C, D] > [E, F, G, H]: Then we know I, J, K, L are all true weight. We now need to divide the remaining 8 balls into groups of 2 balls in a single weighing. To do this switch two to the other side and replace one ball that stayed on the same side and 1 ball that switched. (2) Weigh [A, I, G, H] against [E, F, C, J]. If [A, I, G, H] = [E, F, C, J]: Either B or D is the fake. (3)Weigh them and take the heavier of the two. If [A, I, G, H] > [E, F, C, J]: The fake is A, E, or F. Since we know E or F would both be lighter, we compare them. (3)Weigh E and F If E = F: A is fake (and heavier). Otherwise the lighter of E or F is the fake. If [A, I, G, H] < [E, F, C, J]: The fake is C, G, or H. Since we again know G or H would be lighter, we compare them. (3)Weigh G and H If G = H: C is fake (and also heavier) Otherwise the lighter of G or H is the fake. If [A, B, C, D] < [E, F, G, H]: Flip all the signs for [A, I, G, H] > [E, F, C, J].

  reply permalink