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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.