How Many Balls Would Be Used?

Date: 8 May 1995 05:00:01 -0400
From: Dana Murray
Subject: Question 2

Consider a knock-out tournament, say tennis or ping-pong, with  n
participants.  The winner of any game goes on to the next round and the
loser retires.  If in any round there is a player without an opponent that
player automatically goes to the next round.  This process is repeated until
the winner of the last game is determined.  Suppose a single new ball is
used for every game.  How many balls have been used in the tournament ?

Date: 8 May 1995 12:05:53 -0400
From: Dr. Ken
Subject: Re: Question 2

Hello there!

First let's consider how we would put the players into a tournament like
this.  If the number of players is a power of 2 like 16 or 32, it's pretty
clear that you'd just have a simple binary tree structure, but what if there
are 83 players?  Let's assume that we just fit the players into the smallest
binary tree structure that they'll all fit into, and just give each unmatched 
player a "bye" (where they proceed on to the next round without a
match) in the first round.  So if there are 83 players, we'll use the
128-player binary tree, which has 64 matches in the first round.  Fill in
the players in the first round so that you have at least one player in each
match (which you can think about by putting the first 64 players into every
second slot; filled, open, filled, open,...) and then start over from the
beginning by filling in the remaining players into the open slots.  So in
this case, once you've filled in the first 64 players, there will be 19
players left to fill out some matches.  So there will be 19 real matches and
45 byes in the first round.

In general, let p be the number of players, and let 2^n be the smallest
power of 2 that's bigger than p.  Then the number of real matches in the
first round will be p - 2^(n-1), and the number of byes will be 
2^(n-1) - (p - 2^(n-1)) = 2*2^(n-1) - p = 2^n - p.

In every round after the first round, all the matches will be full, so in
our example there will be 19 + 32 + 16 + 8 + 4 + 2 = 81 matches.  In
general, not counting the first round, we will have a geometric series with
first term 2, common ratio 2, and n-1 terms.  The formula for the sum of
this series is 2(2^(n-1) - 1)/(2-1) = 2^n - 2.  So if we add the term for 
the first round games, we'll get p + 2^n - 2^(n-1) - 2 games in total.

See if you can figure out how you might find n explicitly in terms of p 
(think logarithms). Thanks for the question!

-K