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?

Not knowing how many of each type of block are in the set of 20, you can separate them into 2 groups with 19 weighings.  Using 1 block as the 'standard', compare it to each other block.  If the standard is aluminum, the other blocks would either weight the same (aluminum) or be heavier (duraluminum).  If the standard was duraluminum, the other blocks would be either lighter (aluminum) or the same (duraluminum).

This method can be improved upon in the following manner:

Separate the 20 blocks into pairs.  With 10 weighings you can determine for each pair if one is heavier than the other or if the two weigh the same.  If one is heavier, separate that pair into the alumunum or duraluminum group.  If they weigh the same place them (pairwise) in a queue to be weighed further.

If after 10 weighings each pair ended up in the queue to be weighed further, choose one block from the first pair as the 'standard' and weigh one from each remaining pair to determine if that pair is heaver/lighter or the same as the standard.  This would take a total of 14 weighings.

If at least one of the pairs were different, then take the aluminum block as the standard and compare it to one of each of the pairs to be weighed further.  This will result in between 11 and 13 total weighings.

Using my method, the highest number of weighings required to sort all the blocks is 14.

Posted by Erik O. on 2005-06-02 20:04:42