The Problem Solving Episode

Here is a very classic math problem revisited using the problem solving techniques presented. I've written out the scratch work earlier but it has been laying at the bottom of my binder for quite some time.


Here is the problem, I have a scale as following and I have 12 balls with identical appearance, so you can't tell one from the other from just looking at it. All the balls have identical physical weight except 1 ball which is slightly lighter in weight than the others. Question is how can you weigh these 12 balls to guarantee to find the slightly lighter ball in fewest attempts with the scale provided?


The data provided to given to us is simple, 12 balls, 1 is different, find it using a scale. The scale plays the most important part in the question as the scale can weigh 2 group of balls at a time and tell if the lighter ball is in one of the group or not. Since the scale is symmetric, the real question is then how to divide the 12 balls into groups and weigh them to achieve the result in the fewest attempts. It is very tempting to just get out a piece of paper and pencil and start simulating the experiments. But that technique may be rigorous and easy to miss a case.

As we follow the problem solving techniques presented, suppose we have N natural number of balls, the question is then to find the following:
(1)find the fewest number of attempts before you are guaranteed to find the different ball
(2)prove that number of attempts is the fewest possible

Using the fact that the scale is symmetric, we know that we'll be weighing the balls in groups. The number of balls in each group can either be factorials of 12 such as 6vs6 or 4vs4vs4 or 3vs3vs3vs3 or even smaller groups. Or the groups can be numbers such as 5vs5. But one thing is for sure that is we'll have to weigh groups consisting of same number of balls, otherwise, it'll be pointless since we won't know if the different in weight is caused by the lighter of ball or the less number of balls on the lighter side. And we'll have to weight in groups less or equal to N/2 which is 6. So we are left with options such as 6vs6 which then can be divided in to 2 groups of 3vs3, or we can have 4vs4vs4 which then can be divided into groups of 2vs2 and we can have 5vs5 as well, which can then be divided into 2vs2 with 1 odd ball out. After we know if the lighter ball is in the group of 2 or 3, we will weigh them either 1vs1 or 1vs1vs1, in which we are guaranteed to find the lighter ball. So now the question is how to divide.

The fact that we are required to guarantee to find the lighter ball limits us from taking chances and required to consider the worst case scenario where applicable. It is natural to want to weigh the balls in groups of 6s because we'll be able to find the lighter group in 1 try. But upon investigation, it takes 2 attempts in total to find the group of 3 balls where the lighter ball resides, either the 12 balls are divided into 6vs6 or 3vs3vs3vs3. And it will take 2 tries to find the lighter ball once the group of 3 balls that contains it is found. Where as if we able to find the group of 2 balls which is lighter than the other groups, it only takes 1 more try to find the lighter ball. Upon discovering this, we look at 1 level up in which the lighter group of 2 balls can be found . 2x2=4 comes into mind.

In fact, upon some brainstorming, one can arrive at the conclusion that we can narrow down the group of 4 containing the lighter ball with one try. If the two groups on the scale show equal weight, then the group left out contains the lighter ball. So upon finding the group of 4s that is lighter, it takes at most 2 tries to find the actual lighter ball, which is a grand total of 3 attempts. 1 less than the 2+2 attempts if the 6vs6 or 3vs3vs3vs3 approach is used.

It seems like a simple question, the correct solution may come to mind right away, or you may work out all the cases and maybe miss a case and not GUARANTEE to find the different ball. But using the above thinking approach, the solution can be derived easily from extending the facts given in the question.

That question seemed all too easy, so I'm going to level it up and change the question so that we don't know if the different ball is lighter or heavier.

The question arises that we have to find a standard ball or a group of standard balls and weigh it against groups that shows different weighs.

Assuming we haven't achieved the above solution, the question's new condition eliminates the 6vs6 attempt since we won't know which group contains the different ball and we will have to eventually break them up into 3vs3vs3vs3 so the initial 6vs6 attempt is wasted.

Since we have to find a standard ball of group of standard balls, we'll attempt 3vs3vs3vs3 and 4vs4vs4 with this fact in mind. If we weigh the first 2 groups of 3 or 4 balls in the first situation, 2 cases are possible. Either the scale is equal and either group can be used as the standard group or the scale shows a difference and the left over group(s) can be used as standard. It seems that we'll have to find the standard group first and then weight it against other groups to find the different group first then divide that group up and weigh against same number of standard balls to find the different ball. Eventhough that seems to be the most straight forward solution, there is a better way that can be achieved through some clever thinking.

Here is a solution that I came up with by weighing in groups of 4 and substituting 3 standard balls to find the different ball.
Again, my solution takes advantage of finding out the group of 3 that contains the different ball, because we only have to weigh 2 out of the 3 to find the different ball.

Number balls 1-12

For the first time, 1-4, on the left side, 5-8 on the right side.

1. If the right heavier then the different ball in the No. 1-8.
2nd step. 2-4 will be removed, 6-8 move to the left from the right side, take 9-11, and place on the right. In other words, on the left side of the 1,6,7,8, 5,9,10,11 on the right side.
1a. If the right is heavier then the different ball have not been touched, either No. 5 or it is No. 1 . If 1 is different, then it is lighter than the standard; if it is 5, then 5 is heavier than the standard weight.
Third step No. 1 on the left side, 2 on the right side.
If the right is heavier, then 1 is the bad ball and the ball lighter than the standard;
If balance, then 5 is the bad ball and the ball is heavier than the standard weight;
This result will not have left as heavy side.
1b, If balance, then bad ball is in 2-4, and lighter than the standard ball.
Third step will be 2 on the left side, No. 3 on the right side.
If the right is heavy, then 2 is a bad ball and the ball is lighter than the standard;
If balance, then 4 is bad ball and the ball is heavier than the standard;
If the left is heavy, then 3 is the bad ball and lighter than the standard ball.
1c. If the left is heavy, then the different ball is in 6-8, and the ball is heavier than the standard weight.
Third attempt, put 6 on the left side, 7 on the right side.
If right is heavy ,then 7 is the bad ball and the ball is heavier than the standard weight;
If balance, then 8 is the bad ball and the ball is heavier than the standard weight;
If left is heavy, then 6 is the bad ball and the ball is heavier than the standard weight.

2. If the scale balance, then the different ball in the No. 9-12.
Second step, 1-3 on the left side, 9-11 on the right side.
2a. If the right is heavy then different ball is in 9-11, and heavier than standard.
Third step will be No. 9 on the left side, 10 on the right side.
If right is heavy, then 10 is the bad ball and the ball is heavier than the standard weight;
If balance, then 11 is the bad ball and the ball is heavier than the standard weight;
If left is heavy, then 9 is the bad ball and the ball is heavier than the standard weight;
2b. If the scale balance, then the difference ball is the 12th.
Third step No. 1 on the left side, 12 on the right side.
If right is heavy, then 12 is the bad ball and the ball is heavier than the standard weight;
The scale cannot balance this time
If left is heavy, then 12 is the bad ball and the ball is lighter than the standard weight;
2c. If left is heavy, then different ball is in 9-11 and lighter than standard weight.
Third step will be No. 9 on the left side, 10 on the right side.
If right is heavy, then 9 is the bad ball and the ball is lighter than the standard weight;
If balance, then 11 is the bad ball and the ball is lighter than the standard weight;
If left is heavy, then 10 is the bad ball and the ball is lighter than the standard weight;

3. If the left were heavy then the different ball is in the No. 1-8.
Next two steps are symmetric to case 1.