Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Determining the Winner of a Tennis Match


Date: 10/9/95 at 14:9:56
From: Jean M. Campbell
Subject: math

How many matches will it take to determine the champion in a tennis 
tournament that started with 89 players?


Date: 10/9/95 at 16:9:4
From: Doctor Ken
Subject: Re: math

Hello!

First of all, let it be known that this is a REALLY cool problem.  I 
think I may have answered it once before, but (gulp) I got a different 
answer than I just got now.  I think the one I've got now is right.

So here's how we do it.  First we say that we're going to hold a 
single-elimination tournament.  Then to find out the number of rounds, 
we need to ask ourselves "what's the smallest round that will hold all 
the players?"

Well, single-elimination tournaments are held using trees known as 
"binary trees."  That means they look like this:

---
    ----
--- 
         -----
---
    ----
---
               ------
---
    ----
---
         -----
---
    ----
---            round 0
         round 1
    round 2
round 3

Notice that in round n, there are 2^n (2 to the n) matches.  Now we have 
to figure out how we're going to put the players into the tree 
structure.  It's easy if we have an exact power of 2; we just plop them 
in in the obvious way. But what about if we have a number that's not a 
power of 2, for example 5 players?  Well, number the players 1 through 
5, and stick them in like this:

 1
---
 5  ----
--- 
 2       -----
---
    ----
---
 3             ------
---
    ----
---
 4       -----
---
    ----
---            round 0
         round 1
    round 2
round 3

In other words, go through and stick them in every second slot.

So in general, what round will we put n players in?  First let me define 
a function for you.  The function \x/ gives the greatest integer less 
than or equal to x.  Then the round we'll put the players in will be 
\Log(n) + 1/ where we take all our Logs to the base 2.  

So how many matches will get played?  We'll first find the number of 
matches in the first round to be played (here, it's round 3) and then 
find the number of matches in all the subsequent rounds.  

The number of matches in the first round to be played will be n - 
\Log(n)/, right?  Try a few examples to see why.

The total number of matches in the subsequent rounds in the case with 5
players will be 1 + 2, and in general will be 1 + 2 + 4 + ... + 
2^\Log(n)-1/. Do you see why?  So the total number of matches played in 
ALL rounds will be: 
(1 + 2 + 4 + ... + 2^\Log(n)-1/) + n - \Log(n)/.

BUT WAIT!  We can actually simplify that expression using the formula 
x^(n-1) + x^(n-2) + ... + x^2 + x + 1 = (x^n - 1)/(x-1).  So the first 
part of our formula will be just (2^\Log(n)/ - 1)/(2-1), which is just
2^\Log(n)/ - 1.  So our final formula is

2^\Log(n)/ - 1 + n - 2^\Log(n)/, which is better known as n-1.

n-1 is a pretty cool answer, don't you think?  So for 89 players, it 
will take 88 matches.  Pretty neat.  Tell all your friends.

-Doctor Ken,  The Geometry Forum


From: Bob McDowell

I saw your answer to the tennis match question and
had to submit a comment.

But first, some well deserved praise.

This Dr. Math stuff is really GREAT stuff.  I'm telling my
students to check these pages.  As far as I'm concerned
these are some of the best pages on the internet.

Why did you go through so much to come up with the
answer?  Since each match in a single-elimination
tournament produces one loser who is then out of the
tournament, there will be only the winner remaining
after 88 matches.  This holds true whether you use
binary trees or any other scheme to schedule the matches.

ABC's bowling tournaments on TV have a single-
elimination tournament for the 5 bowlers with the best
averages during the week.  The tournament is designed
so that #5 plays #4, the winner plays #3, this winner plays
#2, and then the last winner plays #1 for the champion-
ship.  Same number of matches (n-1).

Thanks for listening and again: GREAT PAGES!!!!

    
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/