scale

All posts tagged scale

Balls

Posted by dansonlinepresence on January 10, 2013
Posted in: Math, Programming. Tagged: , , , , , , , , , , , , , , , , , , , , . Leave a comment

Say you have 12 balls which are supposed to have all the same mass except one is a defect and has a different mass. You live in a backward country where the only method of weighing things is balance scales, and their use is highly controlled so you can only do one weighing every 20 minutes. How fast can you find the defect, and whether it’s heavier or lighter?

If you want to solve it on your own, stop reading now.

The naive way to do this is just try things. It’s boring. But trying things makes you think about the situation. For example, there are 24 different possible outcomes. If the balls are numbered 1 through 12, ball 1 could be lighter or heavier; ball 2 could be lighter or heavier; and so on. And you think about the balance scale. Every time you use it, there are 3 different possible outcomes: left is heavier, sides balance, or right is heavier. This means, ideally, you can differentiate between 3 outcomes with 1 weighing, 9 with 2 weighings, and 27 with 3 weighings. So we guess it will take us only 3 weighings to identify the defect. But this isn’t the end of the power of our insight. If we make a weigh, we better make sure there are 9 or less possible outcomes remaining, and if we make 2 weighs, we better make sure there are 3 or less possible outcomes remaining. But even knowing all this, we still basically guess at the solution.

Well, the balance scale has a theme of threes, so why not divide the balls into 3 groups of 4: A, B, and C. We measure A against B. There are 3 possible outcomes, but really the two where the scale doesn’t balance are the same.

Let’s consider what happens when A and B balance. This means the defect lies in C. There are 8 possible outcomes and we have 2 weighs left, so we should be able to discriminate up to 9 outcomes. We take 3 balls from C, let’s call them D, and take 3 balls from A, let’s call them A’, which we know are not defects. Weigh D against A’. If these balance, you know the last ball from C is the defect and you can weigh it against any other ball to find out if it’s heavier or lighter. If D is heavier than A’, it contains a heavy defect. If D is lighter than A’, it contains a light defect. In either case, you can find it by weighing 2 balls from D. If they balance, the third ball is the defect. If they don’t, you know which is the defect because you already know if the defect is heavy or light.

Now say A is heavier than B. Or, say B is heavier than A, but we quickly swap the naming of A and B. It’s the same. Now we have 4 balls that might be a light defect and 4 balls that might be a heavy defect, so 8 outcomes, which is again under the 9 outcomes we can differentiate with our 2 remaining weighings. Now that we know which balls might be heavy and which might be light, we have to be careful in a new way. If we measure A against C, the scale can only give 2 possible answers: A had a defect, or not. But we want 3 possible answers. And we want to make sure for each of the 3 answers, we have only 3 or less possible outcomes. So maybe we measure 2 from A and 2 from B against C, but no, because if they balance we are left with 4 unknowns in the remaining balls from A and B. So maybe we measure 3 from A and 3 from B against — no we can’t do that, because C only has 4 balls. So maybe we mix it up. Take 2 balls from A and 1 from B, call this group E, and weigh against 2 balls from B and 1 ball from A, call this group F. If they balance, we only have 2 balls left from A and B, so only 2 outcomes, and the last weigh would be trivial. If E is heavier, then one of the two balls from A in E could be heavy, or one of the two balls from B in F could be light. Ah. Four possibilities. No good. But only just. Let’s modify what we just had. Make group E as before, but create group G with 1 ball from A, 1 ball from B, and 1 ball from C. Weigh E against G. If they balance, there is 1 ball from A and 2 balls from B remaining; 3 possibilities. Weigh the 2 from A against each other. If it doesn’t balance, the heavier is the defect. If it does balance, the ball from B is a light defect. If E is heavier than G, then either one of the balls from A in E is heavy, or the ball from B in G is light. Take those 3 and you can do what we did with the remaining balls when E and G balanced. If E is lighter than G, then either the ball from B in E is light, or the ball from A in G is heavy. You weigh the one from A in G against a ball from C and if it’s heavier, it’s the defect. If the scale balances, the ball from B in E is light.

Say you had n balls each with a different weight, and you had to rank them from lightest to heaviest. Say also the scale could only accept one ball on each side at a time. The first ball might rank anywhere from first to last, the second ball might rank anywhere from first to last but not the same as the first, the third ball might rank anywhere from first to last but not the same as the first or second, and so on. In total there are n(n-1)(n-2)...(3)(2)(1)=n! possible outcomes. How many weighings do we need to do? Well, the scale will never balance because two balls will never have the same mass. So we can only differentiate between 2^{m} possibilities with m weighs. We have

2^{m} \ge n!
m \ge \log(n!)

Now I don’t really know what the function \log(n!) behaves like. I barely even know what n! is like. So let’s do some mathematical sleuthing.

\log(n!) < \log(n^{n})=n\log(n)

and

\log(n!) > \log\left(\displaystyle\frac{n!}{(n/2)!}\right) > \log((n/2)^{(n/2)})=(n/2)\log(n/2)

So it behaves something like n\log(n). Some of you might have noticed or be interested to know that this is a lot like Stirling’s approximation. And some might have noticed or be interested to know that n\log(n) is commonly stated as the lower limit on the number of comparisons needed to sort a list.