Puzzles, Maths and Algorithms: Defective Balls
For problem 1-3 consider a weighing scale (with two sides) and it only tells which side is heavier (it doesnt tell by how much).
Problem 1: You have 9 balls of same weight, except that 1 ball is defective and it is known to be lighter. Find the defective ball in two weighing.
Problem 2: You have 9 balls of same weight, except that 1 ball is defective (it can be heavier or lighter, we dont know). Find the defective ball in three weighing.
Problem 3: You have 9 balls of same weight, except that 2 balls are defective and they are known to be lighter. Find the defective balls in four weighing.
Problem 4: There are 9 machines that produce the balls. You get 9 balls from each machine during a production cycle. You are given a weighing scale that gives the exact weight. You are told that one machine produced defective balls in a given production cycle. Find the defective machine through a single weight measurement. Assume that a perfect ball weight 1lbs and defective ball weight 1.1lbs.
Problem 5: Consider problem 4. Now assume that the weight of the defective ball is unknown. Now find the defective machine in two weighing.
Problem 6: There are two jars A and B. A contains 50 perfect balls and B contains 50 defective balls. Arrange the 100 balls in the two jars in a way that the probability of randomly picking a ball (by first randomly picking a jar) is maximized.
For the problems 1-3, divide the 9 balls into 3 groups of 3 balls each.
Problem1: Weight group1 and group2. If they are same weight, defective ball is in group3. Pick two balls from group3 and weight them. If they weight same, then the ball left out (from group3) is defective. All other cases are also easy to see.
Problem2: Weight group1 and group2. Then weigh group2 and group3. After these two weighing you would know the group containing the defective ball as well as whether that ball is heavy or light. Then simply pick two balls from the identified group and weight them.
Problem3: This problem has two cases: Case1: One group contains both the defective balls or Case2: Two groups contains one defective ball. Weight group1 and group2. Then weight group2 and group3. After these two weighing you would know whether we have case1 or case2 and also the groups containing the defective balls would be known. Case1 is now easy to solve. Consider case2. Say group1 and group2 contain one defective ball. We can easily find the defective ball in the two groups INDEPENDENTLY in one weighing each (hence 4 weighing).
Problem 4: Let defective machine is x. Pick 1 ball from machine 1, 2 from machine 2, and so on. Total wt would be n*(n+1)/2 + x(.1). Solve for x.
Problem 5: Form two equations. Let defective ball has wt = y. First pick 1 ball from machine 1, 2 from machine 2, and so on. We get equation:
n*(n+1)/2 - x(1-y) = A
Next pick 1 ball from machine 9, 2 from machine 8, and so on. We get equation:
n*(n+1)/2 - (n-x+1)(1-y) = B
We have two equations and two variables. We get x = a(n+1)/(a+b), where a = n(n+1)/2-A and b = n(n+1)/2-B.
Problem 6. Leave one perfect ball in Jar A and put rest in Jar B. The probability of picking the perfect ball is now 1/2 + 49/99. This is clearly the best we can do.
Read full article from Puzzles, Maths and Algorithms: Defective Balls
For problem 1-3 consider a weighing scale (with two sides) and it only tells which side is heavier (it doesnt tell by how much).
Problem 1: You have 9 balls of same weight, except that 1 ball is defective and it is known to be lighter. Find the defective ball in two weighing.
Problem 2: You have 9 balls of same weight, except that 1 ball is defective (it can be heavier or lighter, we dont know). Find the defective ball in three weighing.
Problem 3: You have 9 balls of same weight, except that 2 balls are defective and they are known to be lighter. Find the defective balls in four weighing.
Problem 4: There are 9 machines that produce the balls. You get 9 balls from each machine during a production cycle. You are given a weighing scale that gives the exact weight. You are told that one machine produced defective balls in a given production cycle. Find the defective machine through a single weight measurement. Assume that a perfect ball weight 1lbs and defective ball weight 1.1lbs.
Problem 5: Consider problem 4. Now assume that the weight of the defective ball is unknown. Now find the defective machine in two weighing.
Problem 6: There are two jars A and B. A contains 50 perfect balls and B contains 50 defective balls. Arrange the 100 balls in the two jars in a way that the probability of randomly picking a ball (by first randomly picking a jar) is maximized.
For the problems 1-3, divide the 9 balls into 3 groups of 3 balls each.
Problem1: Weight group1 and group2. If they are same weight, defective ball is in group3. Pick two balls from group3 and weight them. If they weight same, then the ball left out (from group3) is defective. All other cases are also easy to see.
Problem2: Weight group1 and group2. Then weigh group2 and group3. After these two weighing you would know the group containing the defective ball as well as whether that ball is heavy or light. Then simply pick two balls from the identified group and weight them.
Problem3: This problem has two cases: Case1: One group contains both the defective balls or Case2: Two groups contains one defective ball. Weight group1 and group2. Then weight group2 and group3. After these two weighing you would know whether we have case1 or case2 and also the groups containing the defective balls would be known. Case1 is now easy to solve. Consider case2. Say group1 and group2 contain one defective ball. We can easily find the defective ball in the two groups INDEPENDENTLY in one weighing each (hence 4 weighing).
Problem 4: Let defective machine is x. Pick 1 ball from machine 1, 2 from machine 2, and so on. Total wt would be n*(n+1)/2 + x(.1). Solve for x.
Problem 5: Form two equations. Let defective ball has wt = y. First pick 1 ball from machine 1, 2 from machine 2, and so on. We get equation:
n*(n+1)/2 - x(1-y) = A
Next pick 1 ball from machine 9, 2 from machine 8, and so on. We get equation:
n*(n+1)/2 - (n-x+1)(1-y) = B
We have two equations and two variables. We get x = a(n+1)/(a+b), where a = n(n+1)/2-A and b = n(n+1)/2-B.
Problem 6. Leave one perfect ball in Jar A and put rest in Jar B. The probability of picking the perfect ball is now 1/2 + 49/99. This is clearly the best we can do.
Read full article from Puzzles, Maths and Algorithms: Defective Balls
