# Find the heaviest and the second heaviest coins

Each of 32 coins has a different weight. In 35 weighings on a standard balance, find the heaviest and the second heaviest coins.

Clarification: Before you start to identify the heaviest and second heaviest coins, you KNOW that all the coins have different weights but you have no idea what those weights are.

• Are there 32 different weights or we simply don't know? or it doesn't matter? Commented Feb 27 at 20:25
• @CloudCho The question states, Each of 32 coins has a different weight. Commented Feb 28 at 3:38
• ? If I had expected the exact same statement, I wouldn't have asked... Commented Feb 28 at 17:13

First, use a simple "knockout tournament" to find the heaviest coin.
(Divide the coins into sixteen pairs, find the heavier of each pair, then create eight pairs from those and find the heaviest again, and repeat until you have a "winner") in 16 + 8 + 4 + 2 + 1 = 31 weighings.

Now the second heaviest coin must be one of those that was compared directly with the heaviest coin (every other coin is lighter than a coin that is lighter than the heaviest).
There are five such coins (one from each round), and four more weighings are sufficient to find the heaviest of those.

• Would you explain "There are five such coins"? Commented Apr 12 at 22:12
• @CloudCho There are five coins that were directly compared against the heaviest coin in the five "knockout rounds", and those five are the only possible candidates for the second-heaviest.
– fljx
Commented Apr 13 at 14:59

Assuming you can fit more than 1 coin on each side:

Split the 32 in two groups (of 16) and determine heaviest side Take heaviest side, split in two groups (8) and determine heaviest side Repeat (4), and repeat (2) and repeat. Now you have the heaviest coin in 5 rounds.

Second heaviest coin. Split the 31 remaining coins in two groups (15), keep the lone apart Take heaviest of the groups, split in two (7), keep the lone apart Repeat(3),keep lone apart, and repeat (1), keep lone apart. You have candidate one for second heaviest.

Take the 4 kept apart, split in two groups (2). Take heaviest side, split, find heaviest. That is candidate two for second heaviest. Weigh candidate 1 and 2. The heaviest of those is the second heaviest.

The second part of the weighing is determined in 4 steps for candidate 1, 2 steps for candidate 2 and a final step makes seven. So this can be done in 12 steps.

That is, assuming I can fit so many coins on the scale, but so far the question had no limit on the amount of coins we could fit.

• The coins are all different weights, the heaviest coin could be on either side of your first split.
– fljx
Commented Feb 28 at 13:29
• This will not work in all cases. Example: Group 1 with weight units: 85+86+87+...+98+99+120 = 1500 units total. Group 2: weights 100+101+102+...+114+115 = 1720 total weight. Group 2 is heavier in total, and hence with your procedure you will miss the heaviest coin (weight 120 units) in group 1. Commented Feb 28 at 13:39