78 players enter a single elimination tennis tournament (a player is eliminated after 1 loss).

How many matches will be played in this tournament?

May 2, 2006 pm31 8:32 pm 8:32 pm

Is it 7? I know the conversation never took off on the tangent question of calculators, but was it ok for me to use Excel to come up with the answer?

2. May 2, 2006 pm31 9:36 pm 9:36 pm

Kombiz, I think you tried to answer "how many rounds" instead of "how many matches."

The first round can be played without a bye, and there would be 39 matches in that round.

jd

3. May 3, 2006 am31 4:20 am 4:20 am

First round: 39 matches leaves us with 39 winners. Second round: The top player gets a bye, and the other 38 play in 19 matches. At the conclusion of this round we have 20 players in the tournament (19 winners + the top seed). Third round: 10 matches leaves us with 10 winners to continue. Fourth round: 5 matches gives us 5 winners to continue. Fifth round: A bye for the top seed, and the remaining four play in two matches to leave us with 3 in the tournament. Sixth round: Two of the three remaining players play to determine who will enter the final. To be fair, probably the player who rested in the last round should play in this one. Seventh round: The remaining two players battle for the championship. Is there a more elegant way to structure things? Three of the seven rounds had uneven numbers.

So I believe there are 39 + 19 + 10 + 5 + 2 + 1 + 1 = 77 games to be played. Are there always n-1 games in an n-player single-elimination tournament? I guess you’d try to prove this by induction. Start with the simplest case which is n=2, and you need 1 game to settle it. Now we need to show that n implies n+1. Adding another player here for n=3 (give the new guy a first-round bye) requires another game to determine the final outcome. I don’t know if this handwaving is at all convincing. You tell me. Let’s try n=4 just because there’s weird odd/even stuff going on. Uh oh, there only 2 games required there as well. So much for the n-1 games theory.

Where’s the interesting hook in this puzzle that I’m missing?

4. May 3, 2006 am31 4:29 am 4:29 am

Oh, wait. 4 players requires 3 games: in the first round, 2 games, and in the final, 1 game. 2+1 = 3, which is n minus 1. But still don’t know if I’m convinced by my inductive step. What is my reasoning to say that adding a new player to either an even or odd number of players in a tournament always requires adding another game to resolve the champion? I guess in the odd-number case it gives the first-round bye someone to play, and in the even case it creates a new first-round bye which must be resolved (via an additional game later) as soon as there is an odd number of winners from a round (and the basis case there being a final round with a single winner). I guess that’s a little less vague…

Neat problem!

5. May 3, 2006 am31 10:53 am 10:53 am

mrc,

your induction works. I’ll put up an alternate in a few days. And I will be putting similar stuff up, for now, once a week. Math provides a nice counterpoint to the other things I’m blogging.

jonathan

6. May 3, 2006 pm31 1:58 pm 1:58 pm

There is one player (the winner!) remaining at the end of the tournament, so 78 – 1 = 77 players must be eliminated. Since each game eliminates exactly one player, there must be 77 games.

7. May 3, 2006 pm31 7:52 pm 7:52 pm

Nick beat me to the “alternate” solution.

I have collected quite a few puzzles where an “ordinary” approach will come up with an extraordinary solution, (such as 77 in this problem), which in turn might generate a search for a more elegant solution. I will include some of them.

Jonathan

8. May 4, 2006 am31 1:30 am 1:30 am

Nice one, Nick! That’s a very elegant way to deduce the answer — no induction needed.