The moody boxers

Question

A certain group of $n$ boxers is totally ordered by strength; if boxer $X$ is stronger than boxer $Y$, then $X$ wins every single fight against $Y$. The ordering itself is not known to us, and we do not have the slightest idea which boxers are stronger than other boxers.

Unfortunately, these boxers are also very moody; as soon as a boxer has lost a total of six fights in a tournament, he is disappointed and walks home right away (independently of the number of fights that he has won up to that point).

Our task is to organize a sequence of fights in a tournament so that in the end we exactly know the ordering of all $n$ boxers (and hence know for each pair, which of the two is the stronger one).

Question: What is the maximum number $n$ of boxers for which we can settle our task with absolute certainty?

Answer 1

I'll try to show

64 is the most $n$ could be.

• Suppose you were just trying to determine the worst boxer, which is certainly necessary if you want to order all the boxers by ability.

• Suppose also every boxer starts off with a coin. Whenever a boxer wins a match, they give all their coins, including those collected from other boxers, to the loser.

We now fix the matches so the following conditions hold:

1. The boxer with more losses ended up losing, unless
2. It is a boxer with at least one win against a winless boxer. In that case, the winless boxer loses regardless of the number of losses for both sides.

With these two conditions, once you win you will never get any more coins. Since in order to determine the worst boxer everyone except one needs to win, we see that one boxer will end up with all the coins.

I claim that on your $k$th loss, you will have at most $2^k$ coins.

Proof proceeds by induction. This is true to start with if $k = 0$. Otherwise, assume so far you've lost $k-1$ matches, and by induction have at most $2^{k-1}$ coins. If you lose again, then the person you lost to has at most $k-1$ losses, and hence also has at most $2^{k-1}$ coins, and after collecting the winner's coins you will have at most $2^k$ coins.

With at most six loses you can have at most $64$ coins. Since to determine the overall worst boxer requires that boxer collecting all the coins, there can be at most

$64$ boxers.

Answer 2

The answer should be

64.

The strategy:

(Quite similar to the mergesort technique used in sorting numbers)

Divide the boxers into groups of two and let them fight. Create a hierarchy in each of the groups in terms of their ranks.

Now consider the groups of two, two at a time. Let the bottom placed boxers have a fight. The loser of this fight is necessarily placed at the bottom of the four. Now the boxer placed above the one who just lost should fight the winner of the previous match. This strategy ensures that the loser fights only once. Continuing similarly, we can create a hierarchy in the group of four.

Do this for the 16 pairs of groups of two.

Continuing with the same strategy, we can hence, club them into groups of four. Note that the bottom placed ranker has lost only twice.

Similarly, create pairs of the groups of four boxers. We can thus in the end come up with groups of eight boxers where the bottom ranker has lost thrice.

This way we finally end up with a group of 64 where the boxer at the bottom has lost six times. He may then walk away.