14
$\begingroup$

Suppose you have twelve identical-looking balls. Ten of them are the same weight, but one is slightly lighter and one slightly heavier, in such a way that the weight of the lighter and heavier ball add up to exactly the weight of two of the equal-weight balls.

What is the minimum number of weighings on a two-sided scale that are needed to determine which ball is lighter and which one is heavier?


What would the solution be if the weight of the lighter and heavier ball didn't necessarily add up to the weight of two equal balls, but you didn't know whether it was lighter, heavier, or equal to that weight?

$\endgroup$
  • 1
    $\begingroup$ I actually don't know the answer to this one. I just thought of it. $\endgroup$ – Joe Z. Jun 29 '14 at 1:41
  • 1
    $\begingroup$ Nice question, even if you didn't know the answer yourself :P $\endgroup$ – Feeds Oct 7 '18 at 7:45
5
$\begingroup$

We divide the balls into two 6 balls groups, and compare them with scale 1.

  1. Scenario 1 : Assume the weights is not equal, this means that the heavier and lighter ball are not in the same side.(the weight of the lighter and heavier ball add up to exactly the weight of two of the equal-weight balls)

    then, we divide heavier 6-balls groups into two 3-balls group and compare them with scale2.

    we know for sure that the weight is not equal (because there is only heavier ball in this 6-balls group)

    then,we pick the heavier group and compare two of them with scale 3

    • If they have equal weights,then the third one is the heavier one.

    • If they have different weights, we can pick the heavier one easily.

    by repeating weightings number 2 and 3 for the lighter 6-balls groups, we can find the lighter one.

    So, in this scenario, we can find both of balls in 5 weightings.

    I think this scenario is the shortest way.

  2. Scenario 2 : the weight of two group is equal, this means the balls are in the same side... I'm working on this scenario :)

$\endgroup$
  • $\begingroup$ 5 is definitely the minimum, since $12\times11 = 132 > 3^4 = 81$. But I am almost sure that your first step (comparing 6vs6) will Not allow to find the balls in 4 weightings only in the Scenario 2. $\endgroup$ – klm123 Jun 29 '14 at 9:59
  • $\begingroup$ @klm123 - I know, the second scenario is definitely longer , and the answer is 5 $\endgroup$ – Alireza Fallah Jun 29 '14 at 10:24
3
$\begingroup$

For the case where the heavy and light offset exactly, you can solve this in $5$ steps. This is clearly the minimum since there are $12\times 11 = 132 > 81 = 3^4$ possibilities.

Label the balls $a$ through $l$. Weigh $a,b,c,d$ vs. $e,f,g,h$. There are 48 cases where the scale will tip left, 48 where it tips right, and 36 where it stays even.

Tip Left: Either the heavy one is in $a,b,c,d$ or the light one is in $e,f,g,h$ or both. For step 2, weigh $a,b$ vs. $c,d$. If the scale tips left, then one of $a,b$ is heavy (16 cases), tips right, then one of $c,d$ is heavy (16 cases), stays even, then one of $i,j,k,l$ is heavy and one of $e,f,g,h$ is light (16 cases).

If it tipped left, then for Step 3 weigh $a$ vs. $b$, telling you which is heavy. For Step 4, weigh $e,f,g$ vs. $h,i,j$. If it tips, then one of those three is light and you can figure out which in one more weighing. If Step 4 came out flat, then one of $k,l$ is light, and you can determine which in one more weighing.

If Step 2 tipped right, then for Step 3 weigh $c$ vs. $d$ and after that proceed as above.

If Step 2 came out flat, then for Step 3 weigh $e,f,i$ vs. $g,h,j$. If it tips left, then one of $g,h$ is light, and one of $i,k,l$ is heavy, which you can finish in two more weighings. Similarly, if Step 3 tips right, then one of $e,f$ is heavy, and one of $j,k,l$ is light.

If Step 3 came out flat, then the heavy/light combination is one of $i/e, i/f, j/g, j/h$. For Step 4 weigh $i$ vs. $j$ to figure out which is heavy, then either weigh $e$ vs. $f$ or $g$ vs. $h$.

Tip Right: If Step 1 tipped right, then proceed as above, switching the labels around.

Stays Flat: If Step 1 came out flat, then one of the four sets $(a,b,c,d)$, $(e,f,g,h)$, or $(i,j,k,l)$ contains both the heavy and light balls.

For Step 2, weigh $a,e,i$ vs. $b,f,j$. Tip left indicates one of $a,e,i$ is heavy and/or one of $b,f,j$ is light: 15 possibilities. Likewise 15 possibilities to tip right, leaving 6 possibilities Step 2 stays flat.

Tip left: For Step 3 weigh $a,e$ vs. $i,c$. If it tips left, then either $a$ or $e$ is heavy ($c$ cannot be light unless $a$ is also heavy, otherwise Step 2 would not have tipped left). Compare them in Step 4 to determine which is heavy, then weigh the other three from that set in Step 4 to find the light one. Likewise, if it tips right, then one of $i$ or $c$ must be heavy and proceed as above.

If Step 3 remained flat, then none of $a,e,i$ is heavy, and one of $b,f,j$ must be light. Weight $b$ vs. $f$ to determine the light one (if they come out the same, the $j$ is the light one). Then once you know the light one, weigh the other two from that set (not $a, e, $ or $i$), and you are done.

If Step 2 came out flat, then one of the sets $c,d$, $g,h$, or $k,l$ contains both the heavy and light balls. Differentiating between these six possibilities can easily be done by weighing each pair separately, yielding in answer in at most 5 weighings.

Thus, it is always possible to solve the first problem with at most $5$ weighings.

Not perfectly offset: The heavy and light balls together could weigh more than, less than, or the same as two regular balls. This ups the possibilities to $3\times 11 \times 12 = 396$ possibilities, which would thus require at least $6$ weighings to differentiate. On the other hand, we don't need to know whether the combination is heavier or lighter--just which two they are.

The overall strategy is to examine the 396 cases and see what weighings divide them most evenly. So start with weighing $a,b,c$ vs. $d,e,f$, which splits the groups into 147 tip left, 147 tip right, and 102 stay flat. This is much more envenly divided than weighing 4 vs. 4, which yields $168, 168, 60$.

If that tipped left, you might weight $a,b$ vs. $c,g$, yielding a split of $58, 38, 51$. Following this strategy of examining the splits based on different weighings, and keeping the three groups as close together in size as possible, it should be possible to complete in $6$ weighings, but I haven't explored the depth of the problem.

$\endgroup$
1
$\begingroup$

I see from the previous reply this should be doable in 5 weighings. Though, it has been a week and no answer. So, i will post an answer with 6 weighings. I hope i got it right. If the weights are not necessarily equal, it might remove a weighing, but being they can be equal, it shouldn't change much.

Split the balls into 4 groups of 3.

If a group is known to be heavier or lighter, it can be determined by weighing one ball against another.
    If they are equal, the third ball is the heavier or lighter ball.
If they are not equal, the ball that matches the group as heavier or lighter, is the heavier or lighter ball.
This will be referred to as determine(group).


Weigh Group 1 against Group 2. [1]
    If they are not equal, either Group 1 has the heavy ball or Group 2 has the light ball. (If it is the oppsite, we will rename the lighter side Group 1 and the heavier Group 2)
        Weigh Group 1 against Group 3 [2]
            If they are equal, either Group 2 has the heavy ball and Group 4 has the light ball or Group 1 has the light ball and Group 3 has the heavy ball
                Weigh Group 1 against Group 4, they will be unequal. [3]
                    If Group 1 is lighter, Group 1 has the light ball and Group 3 has the heavy ball
                    If Group 4 is lighter, Group 2 has the heavy ball and Group 4 has the light ball
                    Determine(lighter group) [4]
                    Determine(heavier group) [5]
            If Group 1 is lighter, Group 1 has the light ball and Group 4 has the heavy ball.
                Determine(Group 1) [3]
                Determine(Group 4) [4]
            If Group 1 is heavier, Group 2 has the heavy ball and Group 3 has the light ball.
                Determine(Group 2) [3]
                Determine(Group 3) [4]
    If they are equal, weigh Group 1 against Group 3 [2]
        If they are not equal, either Group 1 has the light ball and Group 2 has the heavy ball (see note above) or Group 3 has the heavy ball and Group 4 has the light ball.
            Weigh Group 1 against Group 4, they will be unequal. [3]
                Determine(lighter group) [4]
                Determine(heavier group) [5]
        If they are equal, one of the groups has both balls.
            Weigh 1 ball from each group against another ball from each group, leaving the third from each on the side. [3] (Refer to these as Groups A, B, and C)
                If they are equal, either Group A is lighter and Group B is heavier or vice versa.
                    switch Group B for Group C and weigh again, they will be not equal. [4]
                        Weigh two of the balls from the lighter group (either Group A or Group B) against each other. [5]
                            If they are not equal, the lighter ball is the light ball and it's groupmate is the heavy ball.
                            If they are equal, weigh the other two balls from the lighter group, they will be not equal. [6]
                                The lighter ball is the light ball and it's mate in Group C is the heavy ball.
                If they are not equal, either Group A has the light ball and Group C has the heavy ball, or Group B has the heavy ball and Group C has the light ball. (See note above)
                    Weigh 2 balls from Group A against the other 2 balls from Group A. [4]
                        If they are not equal, weigh the 2 balls from the lighter side against the other. [5]
                            The lighter ball is the light ball and its mate in Group C is the heavy ball.
                        If they are equal, weigh 1 ball from Group B against another ball from Group B. [5]
                            If they are not equal, the heavier ball is the heavy ball and its mate in Group C is the light ball.
                                If they are equal, weigh the 2 remaining balls from Group B against each other. [6]
                                    The heavier ball is the heavy ball and its mate in Group C is the light ball.
$\endgroup$
1
$\begingroup$

This took me longer than I would like to admit, but I believe I have arrived at a solution! Feel free to leave comments, suggest improvements or point out mistakes.

Originally I included logical conclusions, such as "all balls from previous comparison are eliminated", or "both odd balls must be in the same group". I decided to remove them because it was too long. So if you are following the strategy you must grasp these on your own (or let the computer do it for you).

Opposite, symmetrical paths are ignored. So if > and < are symmetrical, Only < will be accounted for. When I do this I add a ! sign (like so < !).

When I use eliminated balls that are known to be genuine (or common, in this case), I put the letter g next to them. This is done strictly for clarity.


  • Split the balls into 3 groups of 4, call them A, B, C.

  • Mark the balls A1, A2, A3, A4, B1, etc…

(1a) A vs B. If ==, go to (2a). If < !, go to (2b).


(2a) A1 and B1 vs A2 and C1. If ==, go to (3a). If < !, go to (3b).

(2b) B1 and B2 vs B3 and B4. If ==, go to (3c). If <, go to (3d). If >, go to (3d) and replace B3 and B4 with B1 and B2, respectively, thereafter.


(3a) A3 vs B2. If ==, go to (4a). If < !, go to (4b).

(3b) A1 and A2 vs B1 and C1. If ==, A1 = L and A2 = H. If <, go to (4c). If >, go to (4d).

(3c) A1 and B1g and B2g vs C1 and A2 and A3. If ==, go to (4e). If <, go to (4f). If >, go to (4g).

(3d) B3 vs B4. If <, go to (4h). If >, go to (4h) and replace B4 with B3 thereafter.


(4a) C2 vs C3. If ==, go to (5a). If < !, go to (5b).

(4b) B3 vs B4. If ==, A3 = L and A4= H. if <, B2 = H and B3 = L. If >, B2 = H and B4 = L.

(4c) A1 and C1 vs B1g and B2g. If <, go to (5c). If >, go to (5d).

(4d) A2 and B1 vs C1g and C2g. If <, go to (5e). If >, go to (5f).

(4e) A2 vs A3. If ==, go to (5g). If <, A2 = L and C1 = H. If >, A3 = L and C1 = H.

(4f) A4 and C2 vs B1g and B2g. If ==, go to (5h). If <, A4 = L and C1 = H. If >, A1 = L and C2 = H.

(4g) A2 vs A3. If <, go to (5i). If >, go to (5i) and replace A2 with A3.

(4h) A1 and A2 and A3 vs C1 and C2 and C3. If ==, go to (5j). If <, go to (5k). If >, go to (5k) and replace A1, A2 and A3 with C1, C2 and C3 respectively.


(5a) B3 vs A1g. If < !, B3 = L and B4 = H.

(5b) C4 vs A1g. If ==, C2 = L and C3 = H. If <, C3 = H and C4 = L. If >, C2 = L and C4 = H.

(5c) A3 vs A4. If <, A1 = L and A4 = H. If >, A1 = L and A3 = H.

(5d) C2 vs C3. If ==, C1 = H and C4 = L. If <, C1 = H and C2 = L. If >, C1 = H and C3 = L.

(5e) B2 vs B3. If ==, B1 = L and B4 = H. If <, B1 = L and B3 = H. If >, B1 = L and B2 = H.

(5f) A3 vs A4. If <, A2 = H and A3 = L. If >, A2 = H and A4 = L.

(5g) C2 vs C3. If ==, A4 = L and C4 = H. If <, A4 = L and C3 = H. If >, A4 = L and C2 = H.

(5h) C1 vs C3. If ==, A1 = L and C4 = H. If <, A1 = L and C3 = H. If >, A1 = L and C1 = H.

(5i) C2 vs C3. If ==, A2 = L and C4 = H. If <, A2 = L and C3 = H. If >, A2 = L and C2 = H.

(5j) A4 vs C4. If <, A4 = L and B4 = H. If >, B4 = H and C4 = L.

(5k) A1 vs A2. If ==, A3 = L and B4 = H. If <, A1 = L and B4 = H. If >, A2 = L and B4 = H.

$\endgroup$
1
$\begingroup$

This is an answer for if the two balls (heavier and lighter) do not balance each other out.

Separate into three groups of four. Weigh two groups against each other.

if they balance, set them aside as normal-weight. Both the heavier and lighter ball must be in the remaining four. Weigh two of the remaining balls against two of those already known to be normal-weight, one at a time. If both weigh equally, you have identified all the normal-weight balls. If one is heavier or lighter, you know which ball it is. Weigh the last two against each other, and identify the balls by elimination (if the heavier has already been found, the heavier of the two is normal-weight, and the reverse). OR weigh two balls against two balls, from the last four, and swap two balls around for a second weighing. If the balance doesn't change, you swapped the normal-weight, and the heavier and lighter are those remaining. If the balance reverses perfectly, you swapped the heavier and lighter, and they can be identified by their sides. If the difference only gets smaller, you swapped the lighter ball for a normal weight ball, and you can find the lighter by which way the difference goes. If the difference reverses, but to a lesser degree - you swapped the heavier ball, and can find the lighter by which way the difference goes. (lesser to greater difference, the lighter is on the opposite side from the heavier after the move; greater to lesser difference, the lighter is the same side as the heavier after the move) The total is found in four attempts for the first case, but just three for the second (if you are certain of your ability to distinguish the differences in the weights perfectly).

If the first eight do not match, then weigh one of the groups against the last group of four.

Any two groups that match can be set aside as normal-weight, and both the heavier and lighter ball is in the third group. The heavier and lighter balls, as in the last scenario, can be separated out of the group of four in three weighings - two of one ball against one normal weight ball and the last two against each other, or in two - two against two and swap one from each side, remembering the degree of difference for each. The total is found in five or four attempts.

If none of the three groups match, the heavier and lighter balls are in different groups. The middle weight group is set aside as normal-weight, as one heavier and one lighter ball will balance accordingly. The odd ball could be separated out of each group of four in two weighings (each of one against one within the group, since it is already known from the group weight whether the odd ball is heavier or lighter). OR, you could weigh one from each group against each other. You might get away with three weighings - if they all balance, the heavier and lighter are the last two (known by their respective groups). If one weighing balances, and two don't - the two that don't contain the heavier and lighter balls. If two balance and one doesn't, though, one more weighing would be needed to determine if the different weight balls were separate or weighed against each other. Either way, best case scenario is four weighings, worst case is six.

If the heavy and light balls do balance each other (in the case that it was not known if they would or not, if it was known beforehand a different strategy may be wiser), and are not in the same groups-of-four, the same procedure would pick out the balls. Since they're in different groups, their ability to combine is not relevant.

If they balance each other and are in the same group-of-four, this will be known after two weighings - since all three groups will balance out. At this point, the balls can be identified in as little as two more weighings in each group at best, and at worst six more weighings (two against two, and swap two balls for the second weighing per group). This means it can be found in as little as four weighings, and as many as eight.

This is an answer for if the balls are known to balance each other out... so then a wiser choice might be to start with four groups of three.

Two weighings (three vs three) will establish if the groups are a different weight. If one balances and one does not, the unbalanced pair contains the relevant balls. If both weighings don't balance, two more (three vs three, just swapping the groups) will give one weighing that balances and one that doesn't - revealing the groups containing the lighter and heavier balls. Two balls in those groups can be weighed against each other, if they balance, the third is the odd ball out, if they don't balance, the relevant ball can be chosen by which group it was in (lighter ball, in lighter group, and reverse). This would give four or six weighings to find the balls.

If the balls are in the same group, then this will be known in two weighings (all four groups balance). Weigh two balls of each group against each other until the group is found, maximum four weighings (it will be the only one with a mismatched balance, which it must have, considering it contains one light, one heavy, one normal-weight). Weigh the last ball against one ball from another group (which must be normal-weight) to determine whether the heavier or lighter ball from the first weighing is normal-weight. The balls would be known in four to seven weighings.

$\endgroup$
0
$\begingroup$

@Alizerah Fallah. You already made a case for 5 weighings, but it's quite horrible. You're splitting the 132(12*11) possible cases into two cases of 36 and one of 60, and give up when the 60-case is hard to solve.

I instead propose a first weighing of 5 vs 5 balls. This splits it into two 45-possibilities cases and one 42-possibilties case.

Weighing 3v3 does so as well.

Thinking about writing a program to bruteforce this, it's quite dishearthening if the asker does not know the answer. I thought OP confirmed that it's doable in 5 in a comment on Alizerah's answer, but he did that himself.

$\endgroup$
0
$\begingroup$

If the lighter and heavier ball add to the same weight of any other pair of balls, then the worst case scenario is that you need 11 weights to find them.

That's because there is always the chance that your division is gonna have both balls in the same group together, giving you an equal weight as the other groups... so you can keep comparing smaller and smaller groups but the worst case will always be that the 2 balls are still in the same group... you won't find out until you weigh 11 times.

This is probably wrong.. but it is my initial thought XD.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Puzzling SE. Please make sure to enclose your answer using the spoiler tag (>!) in order to hide it from others to give them the chance to think and give their own answers. $\endgroup$ – Paul Karam May 2 '18 at 10:40
  • $\begingroup$ @PaulKaram while this is true in general, the other answers on this question don't do that either, probably because of the length. I know that this is hard to see from the review queue :) $\endgroup$ – Glorfindel May 2 '18 at 11:21
  • $\begingroup$ @Glorfindel Yeah it was from the review. I can see now what you mean :) $\endgroup$ – Paul Karam May 2 '18 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.