Teaching math through World Cup soccer

FIFA rules give you a good opportunity to explore combinatorics and logic puzzles.

Now that the U.S. has played England to a draw in the World Cup, it's a good opportunity to use FIFA rules to calculate how many games there have to be in a World Cup.

1. The group stage

First, we have a group stage, where the 32 qualifying teams are placed in 8 groups 4, and in each group, the 4 teams play each other round-robin (i.e., each team plays each other team); each team gets points that way (e.g., 3 for a win, 1 for a draw), and the two teams with the highest number of points in each group advance to the knockout stage. (Because teams can be tied on points, this relies on a number of tiebreaker rules.)

In a round-robin tournament, the number of ways of populating "X plays against Y" when there are n teams is n × (n–1), because you can put n teams in the first spot and n–1 teams in the second spot (because "England plays England" isn't a thing). But when you do that, you're double-counting, because "England plays the U.S." is counted differently than "The U.S. plays England". So we'll just divide by 2, and get n(n–1)/2.

In general, this is the combinatorics concept called "n choose k", where (n,k) = n!/[(n–k)!k!]; here, we're using "n choose 2", which is just equal to n(n–1)/2.

Anyway, that means each group of 4 has 4×3/2 = 6 games, and since there are 8 groups, that makes 8×6 = 48 games.

2. The knockout stage

Next, we have a knockout stage, where the 16 teams are reduced to 1. This is a single-elimination tournament, where the loser in any game is immediately eliminated. (Unlike in the group stage, you can't have ties in individual games, so this requires a way of producing a winner in each individual game, e.g., sudden death overtimes and penalty kicks.)

When the number of teams is a power of 2, then it's easy to produce brackets -- and it's easy to check that with 16 teams, you get a winner with 15 games (i.e., 8 games in the round of 16, plus 4 games in the quarter-final, plus 2 games in the semi-final, plus 1 final game, and 8 + 4 + 2 + 1 = 15). But you can always produce a bracket with a non-power of 2 by using some number of byes.

So, you can ask, how many games would you need in general in a single-elimination tournament if there are n games, where n isn't guaranteed to be a power of 2? You can try creating a sample bracket and counting up the number of games, but how do you know that's the best bracket design? Could you do better? Now what if I gave you a very large number of teams, like 693? Are you going to test out various brackets?

This has long been one of my father Vladimir's favorite logic puzzles. You can cut this particular Gordian knot by observing that, when you have n games, eliminating down to 1 necessarily requires eliminating n–1 participants, and in a single-elimination tournament, playing 1 game necessarily eliminates exactly 1 participant. So the number of games is exactly n–1. If you start with 693 teams, you'll always play exactly 692 games to get a winner.

(There might still be better and worse designs of brackets: for example, the design "A plays B, and then the winner of that game plays every single other team sequentially" is probably not the best design, because then you'll be expecting the best team to play 692 games while every other team only plays 1… and if the worst team happens to play on the last day while the best team is having a bad day, you might get a perverse result. Better to approximate the power-of-2-type brackets, where every team plays up to approximately the log-base-2 of the number of teams (rounding up), and nobody wins unless they've played approximately that number of games (rounding down). But still, as far as the total number of games is concerned… the best bracket and the worst bracket will have exactly the same number of games.)

Anyway, to eliminate 16 teams down to 1, just apply the n–1 rule, and you get 15 games.

3. The third-place contest

But wait a minute, we still have one more game to play. FIFA happens to have a "third-place playoff" game: while the winners of the two semifinal games advance to the final (and are defined as first-place and second-place), the losers of those two semifinal games play one additional game (and are defined as third-place and fourth-place).

Thus, in the 2018 World Cup (which was played in seven different Russian cities), the semifinals involved France vs. Belgium (won by France) and Croatia vs. England (won by Croatia). In the final, France played Croatia (France won), but before that game, Belgium played England (Belgium won).

Now, strictly speaking, this isn't really an accurate ranking, because how do we know that Croatia is #2 while Belgium is #3? What if France and Belgium were the top 2 teams, while Belgium and England would have been ranked #9 and #10 out of the 16 teams in the knockout stage (but the brackets were arranged in such a way that the good teams were all on top but the bad teams were all on the bottom)? There's a sloppiness in defining the final-loser as #2 and the winner-of-semifinal-losers as #3. But hey, everyone likes rankings, even if they're inaccurate.

4. Putting it together?

Putting it all together, we get 48 games in the group stage, plus 15 games in the knockout stage, plus an extra game to determine third place, which makes 64.

Why not just play round-robins, which irons out the effects of having bad days and gives you a more scientific estimate of who's the better team? (Neither system is perfect: single-elimination puts a lot of emphasis on not having bad days, while round-robin involves arbitrary win-to-draw point ratios, e.g., 3:1 for FIFA and 1:0.5 for chess.)

Turns out that, because the round-robin rule is n(n–1)/2, the number of round-robin games you'd have to play increases as the square of the number of teams. With 32 teams, you'd have 32×31/2 = 496 games. That's a lot more than 64!

If you have T = nk teams and you divide those teams into k groups of n, you get kn(n–1)/2 games, but since k = T/n, you can express that as T(n–1)/2 games. With T = 32 and n = 4, that's another way of getting to 32×3/2 = 48 games for the group stage. So, holding the number of teams constant, we're basically linear in the number-of-teams-per-group. We could minimize the number of games by making n = 2, i.e., 16 games (32 games total when you add in the knockout stage and third-place game), i.e., just making it single-elimination all the way back. Or we could maximize the number of games by making n = 32 and actually playing those 496 games.

FIFA has chosen an arbitrary number of groups and then an arbitrary place to start the knockout stage, which gives us 64, a nice compromise between 32 games and 496.