Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to confirm if my answer is correct for the following question:

A conventional knock-out tournament begins with $2^n$ competitors and has $n$ rounds. There are no play-offs for the positions $2,3,..,2^{n-1}$, and the initial table of draws is specified. Give a concise description of the sample space of all possible outcomes.

My answer is: $$\sum_{i=1}^{n} 2^{2^{i}/2}.$$

My reasoning is as follows: For each round, the number of players is $2^n$. The number of matches for each round is $2^n / 2$. Since there can be only a win or loss, the total number of combinations per round is $2^{2^{n}/2}$. Therefore the total number of combinations of outcomes (the total sample space), is the sum of combinations in each round from $1 \ldots n$.

share|improve this question
    
What is the variable in the summation? –  vadim123 Feb 18 at 17:58
    
Corrected the summation. –  I.K. Feb 18 at 18:00
1  
"For each round, the number of players is $2^n$": No it's not. –  TonyK Feb 18 at 18:04

2 Answers 2

up vote 1 down vote accepted

You don't need to sum any complicated series here. Simply observe that each match eliminates one competitor, therefore there are $2^n-1$ matches, each of which has two possible outcomes.

share|improve this answer
    
No! Much more than that! –  TonyK Feb 18 at 18:38
    
Answer is: $2^{2^{n} - 1}$. –  I.K. Feb 18 at 18:52

We have $2^n$ players, so basically there are $\frac{2^n}{2} = 2^{n-1}$ games in the first round. The combination of possible players going to the next round is given by $2^{2^{n-1}}$ because in each game we have two possible winners.

In the second round, we will have $2^{n-1}$ players and $2^{n-2}$ games. Following the same reasoning, the combination of winners is given by $2^{2^{n-2}}$.

And so on, until we reach the final, for which we have $2^1$ possible winners.

Therefore, the number of possibilities we have is given by the summation of all possible outcomes in different rounds:

$\displaystyle \sum_{i=1}^{n} 2^{2^{n-i}}$.

If we take only the power, we can see that it follows a geometric series form, so we can calculate the sum of all powers $= 2^n - 1$

Therefore, the final number of possibilities is $2^{2^n - 1}$.

The explanation of Tony K is much simpler, however I couldn't figure out why the number of games was $2^n - 1$ until I developed this reasoning.

Hope it helps!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.