15
$\begingroup$

A 64-player binary tournament bracket is about to start. You plan to free up your schedule in advance to watch some of the matchups (meaning, you can plan to watch the second semifinal, for example, but you cannot decide to watch one game or another based on the results of previous matches and teams seen). What is the minimum number of matches you must plan to see in order to confidently answer any (well-posed) question of the form, "Who won in the match between Team X and Team Y?"

Example logic/tiny hints:

If it were only a 4-player tournament, merely watching the final would give you all the information you need. If it were an 8-player tournament, watching the final and the semifinals would give you all the information you need. Similarly, watching every round of games after the first in the 64-player tournament consists of $16+8+4+2+1=31$ games, but the actual solution is more efficient than this. The answer can be deduced with only pencil and paper (no computer assistance).

Improve this question
$\endgroup$

2 Answers 2

Reset to default
15
$\begingroup$

I can do it in

21 games. Watch the finals, then two rounds before that (the quarterfinals), then two rounds before that. That makes $1 + 4 + 16$ games total.

This is optimal because:

If there are two consecutive games that I don't watch -- that is, game X feeds into game Y, and I skip both -- then there's a problem. I won't know the winner of game X if they end up losing game Y: both players of game X will have "disappeared" for me, and I have no way of telling which one dropped out in game X and which one made it to game Y.

And because the branches of the tournament are all independent, at least one optimal solution will treat every round uniformly. [see below]

I don't want to watch the 32-game round, since that would lose to the strategy of watching literally every other game. So I skip that round, and must watch the 16-game round as a result.
I don't want to watch the 8-game round if possible, because that would lose to the strategy of watching every remaining game (which would be 4+2+1). So I must watch the 4-game round.
I don't want to watch the 2-game round, so I must watch the 1-game round. (I had to watch that one anyway, of course!)

So this gives me the most efficient strategy: watch the second, fourth, and sixth rounds of the tournament, with 16, 4, and 1 game respectively.

More detailed argument for symmetry:

Say we have an optimal strategy that is not symmetric -- that is, one that treats at least two games in the same round differently. Consider a game where the two subtournaments below that game differ; call this game the "root". Imagine "copying" one of the two subtournaments' schedules, and replacing the other with it -- watching all the games that would correspond to games you would watch in the first one. I claim this process will always keep your schedule valid.

Earlier, I mentioned that if any unwatched game has an unwatched successor, this makes an invalid schedule. The inverse is true as well: if every unwatched game has a watched successor, we can determine all games' results. Every unwatched game can be recovered by looking at its successor.

This "copy" operation cannot generate an unwatched game with an unwatched successor anywhere at the root or above, because it does not change their statuses. Also, any unwatched game at least 2 levels below the root is guaranteed recoverable because the original schedule was valid. This only leaves the possibility of an unwatched game just below the root: however, if this exists, that means the root must have been watched. So the copy operation will not invalidate the schedule.

We can repeat this copy operation until each level is uniform, and each time we apply it, the schedule can only improve. Therefore at least one optimal schedule is uniform across all layers.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ The proof isn't convincing: not every symmetric problem has a symmetric solution. $\endgroup$
    – aschepler
    Commented Jul 6, 2020 at 4:00
  • 2
    $\begingroup$ One possible fix is to argue that if $n$ matches are watched, then every match either has to be watched or has to feed into a watched match. Since watching every match takes care of at most three matches (itself and possibly the two matches feeding into this), we need $3n$ to be at least the total number of matches, $63$. $\endgroup$
    – Ankoganit
    Commented Jul 6, 2020 at 4:22
  • 1
    $\begingroup$ @aschepler I'm not arguing just from symmetry, but from the fact that different "branches" of the tournament are entirely independent. You're right that it was a bit handwavy, though - I've edited to give a better explanation. $\endgroup$
    – Deusovi ♦
    Commented Jul 6, 2020 at 4:38
  • 1
    $\begingroup$ @justhalf The "subtournament" is one of those two games, plus the entire tree of games that lead up to it. By "differ", I mean that their schedules are not the same: that is, you watch a game in one subtournament, but you don't watch its corresponding game in the other subtournament. $\endgroup$
    – Deusovi ♦
    Commented Jul 6, 2020 at 15:41
  • 1
    $\begingroup$ This is indeed the correct answer, if you can accept this line of reasoning regarding the symmetry. Personally I'm a huge fan of Ankoganit's trick, even if it is a bit serendipitous. Another easier fix, I should think, is to simply say "Consider an optimal solution; modify this solution by sliding any round 1 watches to their successors in round 2 (an operation which preserves the goal); any round 3 watches into round 4; etc." and you get exactly the form of highly symmetric solution that Deusovi describes. $\endgroup$
    – Feryll
    Commented Jul 6, 2020 at 16:30
3
$\begingroup$

I arrived at the same solution as Desouvi, but I reasoned it from the other direction.

The final answer is

21 games

To start with, I observe

I must watch the finals, no matter what, since there is no other game that can predict the outcome of that game.

This splits the problem into two smaller problems.

There are now two independent tournaments, each of 32 players.

But since I already know

Who plays in the finals, I know the outcome of those tournaments. However, I still need to know who played in the semifinals, which is equivalent to knowing the winners of the quarterfinals.

I can subdivide the problem again

I can watch no games in the tournaments of 32, and instead look at the four tournaments of 16. Watching the finals (of the tournament of 64) plus knowing the outcomes of the 4 preliminary tournaments of 16 will be sufficient to completely fill in the 2 half-tournaments of 64.

At this point, a pattern emerges:

For a tournament of size N, I can watch the finals, and then recursively solve the four tournaments of size N/4.

I believe this to be minimal because

It is impossible to know the outcome of the Finals without watching them, and watching the Finals of one tournament subdivides the problem into four smaller problems. Since I cannot know in advance which of these four tournaments will produce the two teams in the Finals, I need to know the final outcome of all four of these tournaments. That means I must treat them as identical to the original problem, which means I must watch the "finals" and can then subdivide the tournaments again, recursively.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ This doesn't quite work for a tournament with an odd number of rounds. For example, in an 8-player tournament, you'd watch the finals and the first round for 5 games, but you can do it in 3 by skipping the first round. $\endgroup$
    – Deusovi ♦
    Commented Jul 6, 2020 at 21:02
  • 1
    $\begingroup$ @Deusovi That's right. There's two base cases to the recursion - the tournament of 4 teams (in which I watch only the finals) or the tournament of 8 teams (in which I'd watch the finals and the semifinals). I didn't include that exception because it doesn't come up in the problem as specified. $\endgroup$
    – Tim C
    Commented Jul 6, 2020 at 21:51
  • 1
    $\begingroup$ Well, that doesn't quite work either - in a tournament of 32 people, you'd watch rounds 2, 3, and 5, but you only need to watch rounds 2, 4, and 5. Watching the finals only subdivides the problem into 4 smaller problems if you already accept that you're skipping the semifinals. That happens to be true in the original problem's optimal solution, but it isn't necessarily true in general. $\endgroup$
    – Deusovi ♦
    Commented Jul 6, 2020 at 22:16

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