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?

First of all, we have to assume that "some" means at least one, and that the "rest" also means at least one.  If not for these restrictions, there'd be 2^20 possibilities as to which are duraluminum and which not.  That leaves 2^20 - 2 -- not much different.

Ideally, each weighing would reduce the possibilities by a factor of 1/3: 1/3 of the cases would result in left pan heavy, 1/3 right pan heavy and 1/3 equal pan weights.  That would mean the process would take base-3-log ( 2^20 - 2 ) = 12.61859333528395.... Of course there are no fractional weighings, so ideally it might take as few as 13 weighings.  But possibly there'd be no way of arranging exact 1/3 situations for each weighing (or close enough to allow for 13 weighings).

There is certainly a way of doing this in 19 weighings.  Just weigh block 1 vs. block 2, block 2 vs. block 3, ..., block 18 vs. block 19, block 19 vs. block 20.

So it's somewhere between 13 and 19 weighings.

Posted by Charlie on 2005-06-02 19:54:16