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?
It is possible to identify which blocks are aluminum and which are duraluminum in at most fifteen weighings using this algorithm:
There will be four piles: heavy, light, unknown, and reserve. All the blocks start out in the unknown pile and the algorithm starts at State 1.
State 1
Compare two blocks from the unknown pile.
- If they are not equal, place the heavier block in the heavy pile and the light block in the light pile. Repeat State 1.
- If they are equal, place both blocks in the reserve pile and go to State 2.
State 2
Take two blocks from the reserve pile and two blocks from the unknown pile and compare the pairs.
- If they are equal, place all the blocks in the reserve pile. Repeat State 2.
- If the reserve side is heavier, place the two blocks from the reserve pile and the rest of the reserve pile in the heavy pile and compare the two blocks on the unknown side. If those two are equal, place them in the light pile and if they are not equal, place the heavier block in the heavy pile and the light block in the light pile. Goto State 1.
- If the reserve side is lighter, place the two blocks from the reserve pile and the rest of the reserve pile in the light pile and compare the two blocks on the unknown side. If those two are equal, place them in the heavy pile and if they are not equal, place the heavier block in the heavy pile and the light block in the light pile. Goto State 1.
Eventually the algorithm must halt because the unknown pile is empty. If there are blocks left in the reserve pile, compare one against a known block, if there is one available. If the weighing is equal, all the blocks from the reserve pile equal the known block and if the weighing is not equal then all the blocks from the reserve pile are not equal to the known block.
The best case scenario takes 10 weighings and the worst case scenario takes 15 weighings. The algorithm is extensible to any number of even blocks, where the best case scenario for n blocks take n/2 weighings and the worst case scenario for n blocks take ceil[3n/4] weighings.
Identifying all the blocks in less than 19 weighings
