4
$\begingroup$

You have 64 identical-looking boxes numbered from 1 to 64, each weighing a distinct amount. On a turn, you can tell your friend two numbers between 1 and 64, and she will tell you which of the corresponding boxes is heavier.

  • a) What is the minimum number of turns needed to determine the heaviest box?

  • b) What is the min number of turns needed to determine the heaviest and lightest box?

  • c) What is the min number of turns needed to determine the second heaviest box?

I'm not sure but these are the answers I got

  • a) n - 1 or 63
  • b) n - 1 or 63
  • c) n - 1 or 63

I took smaller n's for e.g. 4, 6 and 8 and tried based on these

e.g. for n = 6, we can have (1,2), (3,4), (5,6), assuming 1,3,5 are the heaviest without loss of generality then we can have (1,3) and finally (1,5) to determine 1 is the heaviest giving us n-1

For part b) and c) we can have (1,2), (2,3), (3,4), (4,5), (5,6) assuming 1,2,3,4,5 are the heaviest without loss of generality then we easily find out the heaviest and 2nd heaviest in n-1 turns again

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Generally speaking, when you have a puzzle like this what they're actually asking for is the minimums number of turns assuming the worst case scenario. Maybe this puzzle is different but I wouldn't have assumed that for B we could just assume that we'd get the one grouping of measurements that let's us find the heaviest and lightest in n-1 weighings. $\endgroup$
    – GoblinGuide
    Nov 20 at 15:47
  • $\begingroup$ Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? $\endgroup$
    – bobble
    Nov 20 at 16:04
  • 1
    $\begingroup$ Regarding the final paragraph: since you don't know the box weights in advance, you will only request the information about those exact pairs if you're extremely lucky. As @GoblinGuide says, you're usually supposed to devise the shortest method that guarantees you'll find the correct result. $\endgroup$
    – Bass
    Nov 20 at 20:23

1 Answer 1

Reset to default
16
$\begingroup$

Oo, I've got this one; these come up a lot while organising board game tournaments.

a) what is the minimum number of turns needed to determine the heaviest box?

63 turns.

Lower bound: To know that a box is the heaviest, every other box needs to have at least one box known to be heavier than it. Each turn will find a heavier box for at most one box that didn't already have one. So 63 turns are necessary.

Upper bound: run a "winner continues" tournament. After the first comparison, there are 62 challengers to go, so 63 turns are enough. (You could also use a knockout tournament, or some other format; the important thing is to only ever compare boxes that are still potential candidates for being the heaviest.)

b) what is the min number of turns needed to determine the heaviest and lightest box?

94 turns.

Run one six-round (6 = log2(64)) knockout tournament for the heaviest, and another for the lightest. They can share the results of the first round that has 32 comparisons. 63 + 63 - 32 = 94.

This is optimal because the first 32 comparisons didn't measure anything twice (so all information is efficiently gathered even in the worst case), and after the 32 comparisons, the field is neatly split and there can be no more interaction between the knockout tournaments.

c) what is the min number of turns needed to determine the second heaviest box?

68 turns.

You can't find the second heaviest without finding the heaviest, so start with a six-round knockout tournament. (63 comparisons.) The second heaviest box was knocked out at some point, and that can only happen in a comparison against the heaviest, so the second heaviest one is one of the 6 boxes that were directly knocked out by the heaviest box. 5 more comparisons (see first spoiler block) will find out which one.

We can't improve on the final 5 turns, because we won't have any information on the relative weights of those six boxes after the knockout tournament: that information doesn't affect finding the heaviest box, and an optimal system for finding the heaviest box will not contain any redundant data.

To finish with an aside, the final paragraph of the previous spoiler block has a somewhat interesting consequence in the real world: it shows that you shouldn't award a silver medal in an unseeded knockout tournament: giving any kind of medal to the other finalist (the last player to be knocked out) is very much unwarranted.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Oh nice. I had never pondered the second & third case, and the linear method clearly does not do them justice! $\endgroup$
    – Matthieu M.
    Nov 21 at 12:51
  • 2
    $\begingroup$ The silver medal thing is a known issue in tournament organising. When we want actual placement for all teams we run something known as double-knockout. The system requires no seeding. Every team plays in every round against a team that has lost the same number of games as they have, until they stand alone. For the final the team that has lost no games plays the team that has lost only 1. 3/4 is the team that's lost 2 against the team that's lost 3. Hence double knockout, once you've lost 2 the highest place you can get is 3rd. $\endgroup$
    – Separatrix
    Nov 21 at 15:29
  • $\begingroup$ @Separatrix yes, there are several tournament systems that will find the second or even third place with some credibility, while avoiding the trouble of running a full round robin. The most popular one is the Swiss system, which has a lot in common with the system that you're describing. (Which seem unlikely to exist in reality, at least strictly as described: I wasn't able to find a number of participants so that the pairings would line up like that, with everyone playing in every round. In a typical double knockout, the winners' bracket gets to skip some rounds, and there's no bronze match.) $\endgroup$
    – Bass
    Nov 24 at 15:49
  • $\begingroup$ @Bass it's never entirely smooth, and some teams will skip some rounds just because the numbers don't add up, the team that loses no matches has a much shorter run than some in the middle if you try to place everyone etc. In the real world it's best only done with small numbers of entries as it can take a long time. The real world also has limited numbers of available pitches so it's less obvious to a casual observer that rounds are being skipped. $\endgroup$
    – Separatrix
    Nov 24 at 15:54

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.