5
$\begingroup$

The following problem is lightly adapted from AoPS.

You have 30 coins of identical appearance but distinct weights. You have only a balance that can rank exactly 5 coins from lightest to heaviest. What is the minimum number of weighings needed to determine the second-lightest coin?

The AoPS post's comments claim that the answer is 8, but the scheme presented actually finds the lightest coin. I have a gut feeling the answer is 10 – each weighing eliminates at most 3 coins from being the second-lightest – but does this reasoning also rule out a scheme with 9 weighings?

Improve this question
$\endgroup$
5
  • $\begingroup$ Related: finding the second-lightest among six. $\endgroup$ Commented Nov 13 at 5:38
  • $\begingroup$ This looks somewhat similar to puzzling.stackexchange.com/questions/123250/… (but clearly no duplicate). Using horses instead of coins makes it a lot more plausible to get the exact ranks among 5. $\endgroup$ Commented Nov 13 at 6:52
  • $\begingroup$ A single weighing can eliminate more than 3 coins. When weighing 5 coins, a single weighing will always eliminate the heaviest 3 as the second lightest. But it may also eliminate coins that were found on previous a weighing to be heavier than one of the eliminated coins (but which wasn't eliminated among the heaviest 3 in that weighing) $\endgroup$ Commented Nov 13 at 14:00
  • 1
    $\begingroup$ Does the problem require only weighing 5 coins at one time, or 5 groups of coins at one time? $\endgroup$ Commented Nov 13 at 15:39
  • $\begingroup$ @MichaelRichardson 5 single coins at a time. $\endgroup$ Commented Nov 14 at 17:04

1 Answer 1

Reset to default
7
$\begingroup$

I believe the following achieves

8 weighings

First,

split the 30 coins into 6 groups of 5, and weigh each group. Only the lightest two coins from each group are candidates for second lightest overall.

Then,

weigh the 5 lightest coins from 5 groups, and sort those groups in that order. This eliminates the 3 heavier groups.

Finally,

we know the relationships below, with arrows pointing from a lighter coin to a heavier one. Weigh the 5 coins marked in blue: the lightest two from the first group, the lightest one from the second group, and the lightest two from the unweighed group. These include the two lightest coins, so take the second lightest among them. A diagram of the 30 coins showing the known relationships

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ This problem, like many others, was scraped for the OpenMathReasoning dataset. The AI system used to provide "given answers" output 9 for this question. Congratulations! $\endgroup$ Commented Nov 13 at 5:57
  • $\begingroup$ It is interesting to note that, about 29% of the time, this will also identify the third-lightest coin - and also interesting to note how unintuitive that percentage was (I had multiple "intuitive" ideas giving answers like 40%, 25% then 1/6 and 1/3 before finally working it out properly to get reveal spoiler25/87 - reveal spoiler1/6 times, the lightest coin is in the unweighed group, where 25/29 of the other places will put the second-lightest in a weighed group, whereas 5/6 of the time the lightest coin is in one of the weighed groups, giving a 5/29 chance of the second lightest coin being in unweighed group) $\endgroup$ Commented Nov 13 at 8:19
  • 1
    $\begingroup$ @Steve This reminds me of a similar problem which is to find the third-lightest coin from 25 in 7 weighings - you weigh the coins in 5 groups of 5, then lightest of each of the 5 groups, which narrows down the possibilities of the third-lightest coin to one of 5, of which it will be the second-lightest. $\endgroup$ Commented Nov 14 at 1:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.