Determining the Winner of a Tennis MatchDate: 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!!!! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/