Ball Weighing Riddle

Question

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.

Answer 1

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.)

Answer 2

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.