1
$\begingroup$

A twist on the classic, "how many weighings to find the odd weight ball in 9 balls".

Suppose there is n balls. There are two types of balls. One type weighs less than the other. In the set of balls there is at least one of each ball. What is the least amount of weighing needed to separate the two different set of balls.

I am thinking at least n weighings since we do not know how many of each ball there are.

$\endgroup$
2
$\begingroup$

I'm pretty sure that it takes at most N-1 weighings to determine the relative weight of every ball.

As an example, let's say N=8, with balls B1-B8. We can start by comparing groups of two.

B1 & B2

B3 & B4

B5 & B6

B7 & B8

Now, there are only two possible results from these tests. Either they don't weigh the same, or they do. If the balls are of different weights, we place them into the "heavy" pile or "light" pile accordingly, easy-peasy.

If the balls DO weigh the same, then we just place that group aside for a minute.

Once this first trial is complete, we've done 4 weighings. If the balls are all different, we're done.

If, on the other hand, some or all of those weighings led to the balls being equal, we do another round. I'm going to assume that all of the weighings came up equal, to pursue the worst case scenario. For the next round, we combine the groups from the first round, and weigh them against each other.

B1+B2 vs B3+B4

B5+B6 vs B7+B8

After 6 weighings, we're at the same place as after the first round. If the weights were different, the answer is obvious. If they weighed the same, we do one more trial.

B1+B2+B3+B4 vs B5+B6+B7+B8

And now we know for sure which balls weigh what, in the worst case, with 7 weighings.

(And in all honesty, if the problem states that we KNOW there is at least one ball with a different weight, that last weighing is unnecessary. We wouldn't necessarily know which group was which weight, but we'd be able to separate them.)

$\endgroup$
  • 3
    $\begingroup$ You can also weigh one ball against all the others, which lets you classify all the balls as "equal to the first ball" or "not equal to the first ball" with n-1 weighings. $\endgroup$ – f'' Oct 12 '15 at 18:17
1
$\begingroup$

Nice puzzle. I know there is already an accepted answer, but I thought I would point out N-1 is not always optimal. The below solution separates 8 balls in six weighings.


Take a group of four and call them A, B, C, and D.

Weight AB vs CD, and A vs B.

  1. If AB balance CD and
    1. if A balances B, then all four A, B, C, D weigh the same.
    2. if (say) A is heavier than B, then A and B are known, while C and D are heavy and light in some order.
  2. If (say) AB is heaver than CD and
    1. if A balances B, then A and B are both heavy, and C and D can be known with one more weighing.
    2. if (say) A is heavier than B, then A and B are known, and C and D are both light.

Basically there are two possible results from considering A, B, C, and D. Either all of them can be identified in three weighings, or you know all four balls are the same in just two weighings.

So do the same thing with the other four balls E, F, G, and H. Either you can identify all eight balls in 6 weighings, or you have at least one group of four which are all the same and have only used at most 5 weighings. You can then finish up by weighing A vs. E.

$\endgroup$
  • $\begingroup$ Extending this pattern, you can weigh $n = 2^i$ balls in $3n/4$ weighings. 8 is the first time when this is less than $n-1$. $\endgroup$ – user3294068 Oct 12 '15 at 21:28

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.