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?

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.

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.

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)

howwe achived the final answer. I went the simple route: 128-1, although, like trebob, I first thought 126 rather than 127.The brute force method is a little more complicated, but the one-person-per-match elimination works just as easy.

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.

Well they really are the same solution in binary...

01000000+100000+10000+1000+100+10+1 =

01111111 =

10000000 - 1

Which in decimal is 2

^{7}- 1.cathy :-)

Still, I must admit 128-1 is easier :-)

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.

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.