15
$\begingroup$

You have 68 coins of different weights. Using only a balance scale and the coins themselves, find the heaviest and lightest of the coins with only 100 comparisons.

This puzzle is adapted from The Mathematical circles (Russian Experience).

Improve this question
$\endgroup$
3
  • 15
    $\begingroup$ Sigh. I get out my ten-thousandth of an ounce scale and do it in 68 weightings. $\endgroup$
    – Joshua
    Oct 16, 2017 at 0:40
  • 1
    $\begingroup$ Note: It is possible to prove that the algorithms below are optimal. For any $n$, the minimum number of comparisons to find both the minimum and the maximum of $n$ coins is $\lceil 3 / 2 \rceil n - 2$, and the algorithms below meet this bound exactly (when suitably generalized). $\endgroup$
    – wchargin
    Oct 16, 2017 at 17:55
  • $\begingroup$ The same number of weighings will suffice even if the coin weights aren't all different, provided that one need only find any coin that is tied for maximum and any coin which is tied for minimum. $\endgroup$
    – supercat
    Oct 17, 2017 at 0:52

3 Answers 3

Reset to default
42
$\begingroup$

It seems to me that there's a simpler solution than the one accepted above.

Step 1:

Weigh in pairs, as above. 34 weighings. Now we have 34 "light" coins and 34 "heavy" ones, and we want the lightest of the light and the heaviest of the heavy.

Step 2:

Go through the light coins in order. Pick one; that's your lightest so far. Take another, compare it against lightest-so-far. Take another, compare against lightest-so-far. With $n$ coins you need $n-1$ weighings to find the lightest, so this takes you 33 weighings.

Step 3:

Same for the heavy coins. Another 33 weighings. Done.

The point here is that

the "balanced binary tree" structure is very useful when you want more information besides a single winner, but when all you need is a single winner "any tree will do", including the trivial one I've used above.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Record-keeping may be easier, but the number of weighings is still 34 + 33 + 33, or 100. Why is this "simpler"? $\endgroup$
    – WhatRoughBeast
    Oct 16, 2017 at 4:31
  • 9
    $\begingroup$ @WhatRoughBeast 3 steps vs 11 steps. $\endgroup$
    – Christoph
    Oct 16, 2017 at 6:38
  • $\begingroup$ @WhatRoughBeast Also, no need to think about how the steps where you have an odd number of coins affects the result. $\endgroup$
    – Taemyr
    Oct 16, 2017 at 9:51
  • 6
    $\begingroup$ Right. Just to be absolutely clear, I am not at all claiming that this uses any fewer weighings. Only that it's a simpler and more immediately graspable algorithm. $\endgroup$
    – Gareth McCaughan ♦
    Oct 16, 2017 at 11:13
  • $\begingroup$ The simple approach may also be cleaner than the binary-tree approach if the weights aren't all unique. If two coins compare equal on the first pass, toss one in the garbage and put the other with the other not-yet-compared coins. If a coins compares equal to the minimum-so-far or maximum-so-far on later passes, simply toss it in the garbage. $\endgroup$
    – supercat
    Oct 17, 2017 at 0:54
25
$\begingroup$

I see, it took me too long to fininsh my drawing, but let me present it as additional material to sousben's answer:

elimination scheme for finding heaviest and lightest coins

It's a simple elimination scheme like in tournaments.

Improve this answer
$\endgroup$
10
$\begingroup$

Step 1

Group all coins in pairs, weighing one against the other - 34 weighings. Make one group of the heavier ones, and one group of the lighter ones. You know that the heaviest is necessarily in the first group, and the lightest is necessarily in the second group.

Step 2

taking the 34 "heavier" coins, you make 17 weighings, giving you again 2 groups

Step 3

discard the lighter ones from step 2, and using 9 weighings you will find 8 coins that are at least heavier than one coin

Step 4

discard the lighter ones from step 3, and using 4 weighings, you will find 4 coins that are at least heavier than one coin

Step 5

discard the lighter ones from step 4, and using 2 weighings you will find 2 coins that are at least heavier than one coin

Step 6

one last weighting and you know which one is the heaviest of the 68 coins

Then

repeat Step 2-6 on the "lighter" group from step 1, but this time always choosing the lighter coins and discarding the heavier ones instead

This makes a total of:

34 (step 1) + 2*17 (2) + 2*9 (3) + 2*4 (4) + 2*2 (5) + 2*1 (6) = 100

Improve this answer
$\endgroup$
2
  • $\begingroup$ what if on first step you get equal? $\endgroup$
    – Cockabondy
    Oct 17, 2017 at 14:36
  • $\begingroup$ @Cockabondy The OP says that the coins all have different weight. But to generalize the binary tree strategy: If at some point you compare two coins and they are equal, you can throw both of them away, because you are supposed to find the heaviest (lightest) one. That means the heaviest (lightest) weight must be unique. In such a case a whole branch of the binary tree can be cut and you will get to the result with even less steps. $\endgroup$
    – A. P.
    Oct 19, 2017 at 7:14

Your Answer

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

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