16
$\begingroup$

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.


This puzzle is from a Leningrad Mathematical Olympiad.

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

2 Answers 2

30
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Would you explain "There are five such coins"? $\endgroup$
    – Cloud Cho
    Apr 12 at 22:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – fljx
    Apr 13 at 14:59
1
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ The coins are all different weights, the heaviest coin could be on either side of your first split. $\endgroup$
    – fljx
    Feb 28 at 13:29
  • 6
    $\begingroup$ 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. $\endgroup$
    – theozh
    Feb 28 at 13:39
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Feb 28 at 15:50
  • $\begingroup$ Welcome to PSE (Puzzling Stack Exchange)! $\endgroup$ Feb 28 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.