Winning at Wimbledon
Order of play notice at the Wimbledon championships 2004. Photo taken by Matthew Mayer and released under GFDL
Here in the UK the strawberries are finally in season and that can only mean one thing: Wimbledon! Starting on the 22 June, 128 women and 128 men will battle it out for the women's and men's singles titles over a fortnight. Will this be the year for a British champion? Plus can't tell you that, but we can help you while away those hours of rain-delay with some Wimbledon maths...
In each round of the women's and men's singles events the players are paired off, and the winners of these matches proceed onto the next round. The final round, consisting of a single match, decides the title. How many matches will the champion play? How many matches are played in the whole event?
What if there were 1024 players in each event? What can you say about an event with 2n players?
Solution
In each of the Wimbledon singles events, the rounds are as follows:
- Round 1: 128 players playing 128/2 = 64 matches;
- Round 2: 64 players playing 64/2 = 32 matches;
- Round 3: 32 players playing 32/2 = 16 matches;
- Round 4: 16 players playing 16/2 = 8 matches;
- Round 5 (quarterfinal) : 8 players playing 8/2 = 4 matches;
- Round 6 (semifinal): 4 players playing 4/2 = 2 matches;
- Round 7 (final): 2 players playing 2/2 = 1 matches;
64 + 32 + 16 + 8 + 4 + 2 + 1 = 127 matches.
We started with 128 = 27 players, and eliminated half the players at each round until we were left with 1 player after the seventh and final round. If there were 1024 = 210 players in an event, the same process would take 10 rounds, and the champion would play 10 matches. But what about the total number of matches? It is equal to
502 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 1023 matches.
The other way to think about this is that every player loses one, and only one match, apart from the champion. And every match played has one, and only one loser. Therefore if there are 1024 players, exactly 1023 players will lose a match, and we know that a total of 1023 matches were played in the event.
But what about an event with 2n players? From our arguments above, the champion would play n matches to win the title, and a total of 2n-1 matches would be played during the event.
You might have noticed that the total number of matches suggests that the sum of matches in each round is equal to one less than the total number of players. That is:
![\[ \sum _{i=1}^{n} 2^{i-1} = 2^ n - 1 \]](/MI/bf2d768107f08ef65149bcfd3a3066cf/images/img-0001.png) |
In fact, we can prove this is true for all positive integers n using induction. The statement is true when n=1 as
![\[ 2^0 = 1 = 2^1 - 1. \]](/MI/8d894abe3cf3dd19a8993045ad0bfe65/images/img-0001.png) |
If we assume it is true for n-1 and consider the sum up to n, then:
![\[ \sum _{i=1}^{n} 2^{i-1} = 2^{n-1} + \sum _{i=1}^{i-1} 2^{n-1}. \]](/MI/01281721f081bac022fcb812001e1bbb/images/img-0001.png) |
And, since we have assumed that the statement is true for n-1:
![\[ 2^{n-1} + \sum _{i=1}^{i-1} 2^{n-1} = 2^{n-1} + 2^{n-1} - 1 = 2^ n - 1, \]](/MI/778daaf2425cec19b4b2b5d9b5243272/images/img-0001.png) |
and we have proved that the statement is true for all positive integers n! Game, set, and match!
Back to main puzzle page
