Archive for February 2, 2015
Solution to Super Bowl XLIX Problem
In the post When Super Bowl XLIX Starts to Bore You on January 29, you were asked to consider the following problem:
Imagine that the NFL has eliminated divisions, and there are just two conferences with 16 teams each. To simplify things, every team plays the other 15 teams in their conference exactly once each. At end of the regular season, what is probability that every team within a conference has a different record? (Assuming, of course, that each team is equally likely to win on any given Sunday, and assuming that ties are not possible.)
[UPDATE: Upon further review, it seems unlikely that you would have been bored during last night’s game. Unless you hate football and watched just for the commercials, which were terrible; or during the halftime show, which could be described as no better than fine; or during the post-game interviews, although if you’re like me, you were too busy retching over the Patriots’ victory to be solving a math problem just then.]
This is not a trivial problem, and a little exploration is good before you dive into a theoretical solution. Let’s start with a familiar heuristic, Solve a Simpler Problem.
If there were just two teams in the conference, one team would win the game they played. The winning team’s record would be 1‑0, and the losing team’s record would be 0‑1. That is, the records of the two teams would always be different, so P(different, 2 teams) = 1.
If there were three teams in the conference, it gets a little more complex, but not too bad. We can enumerate the outcomes of a season:
| A > B B > C A > C |
A > B B > C C > A |
A > B C > B A > C |
A > B C > B C > A |
B > A B > C A > C |
B > A B > C C > A |
B > A C > B A > C |
B > A C > B C > A |
| A: 2-0 B: 1-1 C: 0-1 |
A: 1-1 B: 1-1 C: 1-1 |
A: 2-0 B: 0-2 C: 1-1 |
A: 1-1 B: 0-2 C: 2-0 |
A: 1-1 B: 2-0 C: 0-2 |
A: 0-2 B: 2-0 C: 1-1 |
A: 1-1 B: 1-1 C: 1-1 |
A: 0-2 B: 1-1 C: 2-0 |
Of the eight possible outcomes, six result in the three teams having different records. That gives P(different, 3 teams) = 3/4.
Unfortunately, the number of possible outcomes jumps pretty quickly. With four teams, there are 64 possible outcomes, and I don’t have the time or energy to list them all here. You’ll either have to trust me, or you can write them out yourself. Of those 64, it turns out that 24 of them result in different records for all the teams. So, P(different, 4 teams) = 24/64 = 3/8.
By this point, you may have noticed a pattern. Or maybe not; it’s subtle.
So let’s start thinking theoretically.
Pick one of the teams. The probability that the first team you pick wins all its games is (1/2)15.
Then pick a second team. This team has one loss guaranteed, since the first team was undefeated. So, the probability that the second team wins its 14 remaining games is (1/2)14.
Then pick a third team. This team has two losses guaranteed, and the probability it will win its 13 remaining games is (1/2)13.
And so on.
The next-to-last team has a probability of (1/2)1 of winning its one remaining game.
And the last team has a probability of (1/2)0 of winning its zero remaining games. Which is a little weird, admittedly, but I include it here for completeness.
Now the kicker: There are 16! ways to choose the order of the teams.
So the probability of 16 teams each finishing with a different record is
Which is to say, it’s not impossible… but nearly so.
