Twenty metal blocks are of the same size and external appearance; some are aluminum, and the rest are duraluminum, which is heavier.

Using a pan balance to determine how many blocks are aluminum, what is the minimum number of weighings to be done?

The lower bound is 13, since 3^13 exceeds 2^20, but 3^12 does not.

Each weighing consists of weighing up to ten blocks against an equal amount of other blocks.

What is the best option (particularly for the first weighing)?

Here is a chart showing the number of possibilities left over after seeing the results of weighing N blocks against N others.

N / balanced / not balanced
1   524288     262144
2   393216     327680
3   327680     360448
4   286720     380928
5   258048     395264
6   236544     406016
7   219648     414464
8   205920     421328
9   194480     427048
10  184756     431910

Given these large numbers, I assumed that the cases where all the blocks are aluminum or are all duraluminum are negligible, so I didn't ommit them.

If we are to reach that lower bound of 13 weighings, we must never be left with more than 3^(13-n) possibilities after the nth weighing.  Though all of the above moves leave less than 3^12 possibilities (531441), some may be more likely than others to succeed as starting moves.  Weighing 2 vs 2 or 3 vs 3 seems best.

Now that the basics steps have been done, I am searching for an elegant leap to the finish line.

I couldn't help but notice that the exact number 327680 appears twice in the cart above.  Interesting, eh?

Edited on June 3, 2005, 9:54 pm

Posted by Tristan on 2005-06-03 21:53:08