2

I am stuck on the following question...

Suppose n people are playing in a tournament where n is a power of two so that it creates an even bracket.

In the first round each player is paired with another player, only the winner of each pair go on to the next round.

How many rounds will there be in the tournament until it finishes?

I have to create an equation in terms of n but I have been messing around with some numbers and can't figure this one out.

amWhy
  • 209,954
  • Try thinking about it this way: Given $n=2^k$ players, how games are played each round and how many players are eliminated in each round? – MM8 Jan 26 '18 at 15:32
  • @TimonG. There would be 2^k/2 games played and 2^k/2 players eliminated (half) –  Jan 26 '18 at 15:34
  • And halfing the number of players if the number of players in round $1$ is $n_1=2^k$ means $\frac{n_1}{2}=\frac{2^k}{2}=2^{k-1}=:n_2$ with $n_2$ being the number of players in the round $2$. Can you take it from here? How many times until only $2$ players are left? – MM8 Jan 26 '18 at 15:37

2 Answers2

1

If the people are $n=2^k$, to finish you need $k$ rounds (only one winner remains).

EG

$$n=16=2^4$$

  • after first round $\to$ 8 people
  • after second round $\to$ 4 people
  • after third round $\to$ 2 people
  • after forth round $\to$ 1 winner
user
  • 154,566
  • wouldn't 16 players mean 4 rounds? 1 round to get to 8, 1 round to get to 4, 1 to get to 2, and then a last to get the winner? –  Jan 26 '18 at 15:39
  • ok if you are looking for a single winner the number of step is k! – user Jan 26 '18 at 15:40
  • Isn't this only valid when $n$ is a power of 2? How would you determine it when $n$ is not a power of 2? Would you seek $k$ such that $2^k$ is the smallest power of 2 greater than n? i.e., we'd want to find $n = 2^m$ and the answer is $k = ceiling(m)$? – 24n8 Mar 30 '21 at 19:33
0

This is something I came up with on my own:

y=x^n where y is the the number of player/ teams, x is the divisor in the ratio of players/ teams that are eliminated each round, and n is the number of rounds.

So, if there are 64 teams and half are eliminated each time:

64=2^n (64/2/2/2....)

log2(64) = n

log(64)/log 2 = n

My only issue is it doesn't seem to work when there are more complicated situations, such as groups and round robin. It seems like the logic should still apply but I can't get it to work. For instance, a chess tournament I was in a while back had 222 people in it, groups of 6, and 3 moved on each time. I used a fraction 6/3, or 2, to represent the number of people that were eliminated each time.

log(222)/log(6/3)=n

7.79 = n, so there should be 7-8 rounds. Except there were 6. I think the reason for this is because since the number of players was cut in half each time, and 222 is not a multiple of 2, it caused the average ratio of players eliminated each round to be off slightly, therefore causing the number of rounds to be wrong. If we solve for the average ratio of players eliminated each round, then that will show if I am correct. My question is, "Is there a way to know what this average is going to be so that you can make an accurate prediction?"

222=x^6

6√(222) = 2.4607, which is more than the 6/3 or 2 that I first calculated. In other words, over the course of the tournament, the number of players was divided by 2.4607 each round, not 2.

user979834
  • 1