pageok
pageok
pageok
[Puzzleblogger Kevan Choset, September 13, 2005 at 12:11pm] Trackbacks
Elimination Tournaments:

Some variation on this was sent to me by a few different readers. Here's my own take:

The U.S. Open Men's Singles draw contained 128 people. Each round was single-elimination, meaning that two people played each other, and the loser was immediately disqualified and the winner moved on to the next round. How many TOTAL matches were played before Roger Federer was named the champion on Sunday? How did you calculate this?

MR:
127. One game per person eliminated.
9.13.2005 1:15pm
LG:
I'm surprised at how much easier this question is than the others I've seen on this site. The total number of matches in a single-elimination tournament is always equal to (2^n)-1, where "n" is the number of rounds. Here the number of rounds is 7, so the answer is 127. It's also equal to the number of entrants in the tournament minus 1.
9.13.2005 1:15pm
alkali (mail) (www):
127. Each match eliminates one participant, and all but one of the 128 participants were eliminated.
9.13.2005 1:15pm
guest:
I come up with 127, figuring 64 matches played 1st round, then 32 matches, then 16, then 8, then 4, then 2, then the final match. Add them all up, you get 127. But this seems too easy... is there some trick I'm missing?
9.13.2005 1:16pm
rbj:
127.
First time I came across this question, I used the brute force method. 128 people divided by 2 per match = 64 matches the first round. Do it again and again, until only one person is left, who can't play, um, a match, with himself. Now I just remember that in a single elimination tournament, the number of matches is one less than the number of people/clubs entered.
9.13.2005 1:18pm
Eduardo S:
127 matches. Assuming that this is a 2-person game (I'm a computer geek, not a jock), the first round is 64 games of 2 people each; then 32, 16, 8, 4, 2, 1.
9.13.2005 1:19pm
Kristian (mail) (www):
Assuming all scheduled matches were 'played' and that we aren't counting women's and doubles mathches, 127 matches. As pointed out, 127 men had to lose before Federer could be cowned champion.
9.13.2005 1:19pm
trebob99 (mail):
Maybe I'm being too techincal, but the question asks for the number of matches played, "BEFORE Roger Federer was named the champion." So, wouldn't that be 126?
9.13.2005 1:23pm
Chris C.:
trebob99>> Federer can only be named the champion after he wins the final match, so there are 127 matches played. AS several have mentioned, I've always used "In a tournament with n players, each match eliminates 1 person, so n - 1 matches are played."
9.13.2005 1:35pm
LG:
In response to trebob99, the number is still 127. Federer was "named" the champion AFTER he won his last match, which eliminated his opponent (Agassi). The insight that all opponents but the champion need to be eliminated is a good one; since this is single-elimination, there are 127 people who didn't win, and 1 person who did win. Each of these 127 people was eliminated in a separate and unique match.
9.13.2005 1:36pm
... (mail) (www):
# of players - 1 is always the answer. Even if there are byes, it still holds. In some tournaments there are 56 player draws, where the top 8 seeds would get a 1st round bye. The number of matches is still 55.
9.13.2005 1:38pm
John B. (mail):
I thought it was too easy, too. 127. Every match must eliminate one player. Only the Champion is not eliminated. Thus the number of players minus one.
9.13.2005 1:53pm
HC:
127 - by the half+half+half method, and then knowing that that would iterate out to one less than the original sum, rather than the more elegant observation that 127 people had to be eliminated.
9.13.2005 2:09pm
steveh2 (mail):
Same reasoning works for double elimination tournaments --if you start with 128 entrants, 127 will be eliminated. Because each ends up with 2 losses, it takes 254 matches to eliminate those entrants.

But if you're doing it for a double elimination tourney, you have to remember that the ultimate winner will have either 0 losses or 1 loss, so it will take either 254 or 255 matches for a 128-entrant double-elimination tourney.
9.13.2005 2:22pm
uh clem (mail):
Too easy. You could have dressed this simple concept up into a nice puzzle:

10,000 people sign up for a single elimination playoff. Opponents are chosen for each round as follows: All players place their names into a hat and draw for their opponent. If they draw their own name, they get a bye for that round. If they draw a player that's already been paired up, they draw again without placing that name back into the hat.

At the end, one player remains and is crowned the champion. How many games are played in total? (ANS: one game per player eliminated or 9,999.)

(Leave aside the fact that this process may never terminate if players keep drawing their own names - the probability of this approaches zero as the number of rounds goes up)
9.13.2005 2:27pm
Paul Zummo (mail) (www):
It seems that Kevin is more interested in how we achived the final answer. I went the simple route: 128-1, although, like trebob, I first thought 126 rather than 127.
9.13.2005 2:53pm
Paul Zummo (mail) (www):
And yes, I know 128-1= 127, not 126, but I had the same thought as trebob about the wording of the question.
9.13.2005 2:56pm
Brian Day (mail):
Martin Gardener published a variation of this problem many years ago. In it the total number of entrants was 127. Everyone was pared up. If there was an odd number of players, then the odd player got a bye (I don't remember the mechanism for determining who gets the bye). So in the first round, there would be 63 matches and 1 bye. How many matches were played?

The brute force method is a little more complicated, but the one-person-per-match elimination works just as easy.
9.13.2005 3:05pm
Kevan Choset (mail):
Yes, I was looking for the method. I figured that a lot of people would do the 64+32+16+...+1 method, which, while very easy (as many of you pointed it out), isn't as easy as simply 128-1.

I was going to follow up with a problem about an odd number of people and byes and a problem about double elimination, but it seems you've already posted those yourself.
9.13.2005 3:57pm
Brian G (mail) (www):
127. I subtracted the number of idiotic things said by Ted Kennedy with those said by Joe Biden in the last 20 years. Next time ask a hearder question.
9.13.2005 4:35pm
cathyf:

Yes, I was looking for the method. I figured that a lot of people would do the 64+32+16+...+1 method, which, while very easy (as many of you pointed it out), isn't as easy as simply 128-1.


Well they really are the same solution in binary...
01000000+100000+10000+1000+100+10+1 =
01111111 =
10000000 - 1
Which in decimal is 27 - 1.

cathy :-)
9.13.2005 4:47pm
Jason DeBoever (mail):
hehe, I did it the same way as cathy. As a professional geek I immediately saw 128 as power of two, the largest number that you can hold in a 7 bit field. And, well, if you've worked with bitmasks enough, the rest is pretty immediate.

Still, I must admit 128-1 is easier :-)
9.13.2005 5:20pm
Adam (mail) (www):
When I was a high school mathlete in the mid-1980s (and, really, how often does one get to say that?), I remember a similar question in a finals round -- it was, like, a 29-team single elimination tournament, and while everyone else was furiously trying to work out the brackets, I just substracted one from the number of teams.
9.13.2005 5:33pm
Amy:
When I was a high school mathlete in the late 1990's I learned the formula 2^0+2^1+2^2+...+2^n=2^(n+1)-1. I used that trick.
9.13.2005 7:28pm
Jake Thomas (mail):
This is an old Car Talk puzzler. If those two MIT trained engineers can figure it out, it should be easy for a bunch of lawyers.
9.13.2005 7:57pm
Kevan Choset (mail):
Just to clarify, the "simple" reason that the answer is 127 is that if 128 people start, and 1 person remains, then 127 people lost, which required 127 matches.

The fact that 1+2+4+...+2^n = 2^(n+1)-1 will help you do the addition the long way, but that's distinct from the "tricky" way. The "tricky" way doesn't involve adding powers of 2 at all, and also allows you to answer more complicated questions as how many matches are in a 123,456,789 person tournament with byes.
9.13.2005 8:09pm
statfan (mail):
Assume that the purpose of the tournament is to determine the world's best tennis player. Further, assume that luck is a factor, and that the best player will only win in 90% of games, rather than all the time (as single elimination assumes). How many matches are needed to be 99% certain of which player is best?
9.13.2005 8:35pm
Edward Lee (www):
On a slightly related note, "triple-elimination" tournaments (where first, second and third-place finishers must be determined) can eliminate some teams after two losses. (An example of such a bracket is here; click on "open division".)

Suppose 1 plays 16 and 8 plays 9 in the first round, with the winners and losers playing each other in the next round. If 16 and 9 lose, play each other in the next round, and 16 loses, then 16 has lost to 1 and 9. If one accepts the transitivity of losing, then 16 has also "lost" to 8, and thus it is safe to eliminate 16 from the tournament.
9.13.2005 11:37pm