All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Twenty metal blocks (Posted on 2005-06-02)
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?

 See The Solution Submitted by pcbouhid Rating: 3.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Identifying all the blocks in less than 19 weighings | Comment 17 of 18 |

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.

 Posted by Brian Smith on 2005-06-07 21:26:13

 Search: Search body:
Forums (0)