Weighings - Puzzle Prime

12 Balls, 1 Defective

Section: Brain Teasers Category: Deduction

Difficulty: Hard Tags: Weighings

You have 12 balls, 11 of which have the same weight. The remaining one is defective and either heavier or lighter than the rest. You can use a balance scale to compare weights in order to find which is the defective ball and whether it is heavier or lighter. How many measurement do you need so that will be surely able to do it?

SOLUTION

It is easy to see that if we have more than 9 balls, we need at least 3 measurements. We will prove that 3 measurements are enough for 12 balls.

We place 4 balls on each side of the scale. Let balls 1, 2, 3, 4 be on the right side, and balls 5, 6, 7, 8 on the left side.

CASE 1. The scale does not tip to any side. For the second measurement we place on the left side balls 1, 2, 3, 9 and on the right side balls 4, 5, 10, 11.

If the scale again does not tip to any side, then the defective ball is number 12 and we can check whether it is heavier or lighter with our last measurement.

If the scale tips to the left side, then either the defective ball is number 9 and is heavier, or it is number 10/11 and is lighter. We measure up balls 10 and 11 against each other and if one of them is lighter than the other, then it is the defective one. If they have the same weight, then ball 9 is the defective one.

If the scale tips to the right side, the procedure is similar.

CASE 2. Let the scale tip to the left side during the first measurement. This means that either one of the balls 1, 2, 3, 4 is defective and it is heavier, or one of the balls 5, 6, 7, 8 is defective and it is lighter. Clearly, balls 9, 10, 11, 12 are all genuine. Next we place balls 1, 2, 5, 6 on one side and balls 3, 7, 9, 10 on the other side.

If the scale tips to the left, then either one of the balls 1, 2 is defective and it is heavier, or ball 8 is defective and lighter. We just measure up balls 1 and 2 against each other and find out which among the three is the defective one.

If the scale tips to the right, the procedure is similar.

If the scale does not tip to any side, then either the defective ball is 4 and it is heavier, or the defective ball is 8 and it is lighter. We just measure up balls 1 and 4 against each other and easily find the defective ball.

Unknown Author July 10, 2022

3 Comments

9 balls, 1 defective

Section: Brain Teasers Category: Insight

Difficulty: Advanced Tags: Weighings

You have 9 balls, 8 of which have the same weight. The remaining one is defective and heavier than the rest. You can use a balance scale to compare weights in order to find which is the defective ball. How many measurements do you need so that you will be surely able to do it? What if you have 2000 balls?

SOLUTION

First, we put 3 balls on the left side and 3 balls on the right side of the balance scale. If the scale tips to one side, then the defective ball is there. If not, the defective ball is among the remaining 3 balls. Once left with 3 balls only, we put one on each side of the scale. If the scale tips to one side, the defective ball is there. If not, the defective ball is the last remaining one. Clearly we can not find the defective ball with just one measurement, so the answer is 2.

If you had 2000 balls, then you would need 7 measurements. In general, if you have N balls, you would need to make at least log₃(N) tests to find the defective ball. The strategy is the same: keep splitting the group of remaining balls into 3 (as) equal (as possible) subgroups, discarding 2 of these subgroups after a measurement. To see that you need no less than log₃(N) tries, notice that initially there are N possibilities for the defective ball and every measurement can yield 3 outcomes. If every time you get the worst outcome, you will make at least log₃(N) tries.

Unknown Author March 1, 2021

2 Comments

68 Coins, 100 Weighings

Section: Brain Teasers Category: Insight

Difficulty: Advanced Tags: Weighings

You have 68 coins with different weights. How can you find both the lightest and the heaviest coins with 100 scale weighings?

SOLUTION

1. Compare the coins in pairs and separate the light ones in one group and the heavy ones in another. (34 weighings)
2. Find the lightest coin in the first group of 34 coins. (33 weighings)
3. Find the heaviest coin in the second group of 34 coins. (33 weighings)

Unknown Author September 22, 2019

2 Comments

Gold and Nickel

Section: Brain Teasers Category: Deduction

Difficulty: Expert Tags: Weighings

You have 15 identical coins – 2 of them made of pure gold and the other 13 made of nickel (covered with thin gold layer to mislead you). You also have a gold detector, with which you can detect if in any group of coins, there is at least one gold coin or not. How can you find the pure gold coins with only 7 uses of the detector?

SOLUTION

First, we note that if we have 1 gold ball only, then we need:

1 measurement in a group of 2 balls
2 measurements in a group of 4 balls
3 measurements in a group of 8 balls

Start by measuring 1, 2, 3, 4, 5.

If there are gold balls in the group, then measure 6, 7, 8, 9, 10, 11.
- If there are gold balls in the group, then measure 5, 6, 7.
  - If there are no gold balls among them, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 8, 9, 10, 11, so we can find the gold balls with the remaining 2 measurements.
  - If there are gold balls in 5, 6, 7, then measure 5, 8, 9. If there are gold balls there, then 5 must be gold, and we can find the other gold ball among 6, 7, 8, 9, 10, 11 with the remaining 3 measurements. If there is no gold ball among 5, 8, 9, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 6, 7, so again we can find them with only 3 measurements.
- If there are no gold balls in the group, then measure 5, 12, 13.
  - If there are no gold balls among them, then measure 14, 15. If none of them is gold, then measure individually 1, 2, and 3 to find which are the 2 gold balls among 1, 2, 3, 4. Otherwise, there is a gold ball among 1, 2, 3, 4, and among 14, 15, and we can find them with the remaining 3 measurements.
  - If there are gold balls among 5, 12, 13, then measure 5, 14, 15. If none of them is gold, then there is a gold ball among 1, 2, 3, 4, and a gold ball among 12, 13, so we can find them with 3 measurements. Otherwise, 5 is gold, and again we can find the other gold ball among 1, 2, 3, 4, 12, 13, 14, 15 with 3 measurements.
If there are no gold balls among 1, 2, 3, 4, 5, then we measure 6, 7, 8.
- If there are gold balls in the group, then measure 9, 10, 11, 12, 13.
  - If there are no gold balls among them, we measure individually 6, 7, 8, 14.
  - If there is a gold ball among 9, 10, 11, 12, 13, then there is another one among 6, 7, 8. We measure 8, 9. If none of them is gold, then we can find the gold among 6, 7, and the gold among 10, 11, 12, 13, with 3 measurements total. If there is a gold ball among 8, 9, then we measure 10, 11, 12, 13. If none of them is gold, then 9 is gold and we find the other gold ball among 6, 7, 8 with 2 more measurements. If there is a gold ball among 10, 11, 12, 13, then we can find it with 2 measurements. The other gold ball must be 8.
- If there are no gold balls in the group, then measure 9, 10.
  - If there are no gold balls among them, then measure individually 11, 12, 13, 14.
  - If there are gold balls among 9, 10, then measure 11, 12, 13, 14. If there is a gold ball among them, then there is another one among 9, 10, and we can find them both with 3 measurements. Otherwise, we measure 9 and 10 individually.

Unknown Author March 24, 2018

11 Comments

Digital Scale

Section: Brain Teasers Category: Insight

Difficulty: Medium Tags: Weighings

You have 10 unlimited piles of balls and one digital scale. All balls in a pile have the same weight, which is an integer between 1 and 9 grams. How many measurements do you need in order to find the weight of the balls in every pile?

SOLUTION

You need only one measurement – take 1 ball from pile 1, 10 balls from pile 2, 100 balls from pile 3, etc., and measure their total weight. The first digit of the number shown on the scale determines the weight of the balls in the 10th pile, the second digit determines the weight of the balls in the 9th pile and so on.

Unknown Author May 16, 2017

0 Comments