Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$12345$ players take part in a knockout tournament. In each round players are paired up; each pair plays a game with the winning player advancing to the next round (no ties). If there are an odd number of players at the start of a round, one is randomly selected to automatically progress. This continues until one player is delared champion.

How many games are played in total?

share|improve this question
up vote 37 down vote accepted

In every game one person loses. There is only one winner, so there must be $12344$ losers. Therefore there are $12344$ games.

share|improve this answer

Let $a_n$ be the number of players at the beginning of the $n$-th round, so that $a_1 = 12345$. Then $a_{n+1} = \lceil \frac{a_n}{2} \rceil$, and the number of games played in round $n$ is $g_n = \lfloor \frac{a_n}{2}\rfloor$.

We thus have the following sequence for $a_n$:

$$12345, 6173, 3087, 1544, 772, 386, 193, 97, 49, 25, 13, 7, 4, 2, 1$$

And the following sequence for $g_n$:

$$6172, 3086, 1543, 772, 386, 193, 96, 48, 24, 12, 6, 3, 2, 1, 0$$

For a total of $12344$ games.

share|improve this answer
6  
You overthought it a bit... – Deusovi Feb 22 at 1:06
    
@Deusovi Right, your solution is much much simpler and more elegant. – Fimpellizieri Feb 22 at 1:37
    
Yes but I would argue that this is the proper math going through calculating how many games for a tree tournament. – Patrick Roberts Feb 22 at 14:54
    
And now you know why the claim at the end of Bloodsport that the real life Frank Dux knocked out 56 consecutive opponents in a single elimination bracketed tournament is so ridiculous – Kevin Feb 22 at 19:40

The answer is 12344.
For any number n it will be n-1.

Explanation

Since this is a knockout round.At the end of each round, half players are getting eliminated.

Let N = 2^k where N is the total number of Players.

In First Round, We will have N/2 matches, in second round N/4 matches. So, at the end of last round we will have 1 match.

Total number of matches = N/2 + N/4 + N/8 + ....2 + 1 which is a standard Geometric Progression Problem.

The Sum will be 1*(2^k - 1)/(2-1) = 2^k - 1 = N-1

Similarly, You can generalize this to any 'N'.

What If N is not power of 2 ?

For Generalizing it for any N, Remember that we can break any N in powers of 2.

Ex- Let N = 1000,

I can write 1000 = 512 + 256 + 128 + 64 + 32 + 8. Now, Doing as above, We will have 511+ 255 + 127 + 63 + 31 + 7 = 994 matches. We will be left with 6 people.

Similarly, 6 = 2 + 2 + 2 , Then we will have 3 more matches i.e 997 and left with 3 people.

Now for 3 people, split as 2 and 1 which will take 2 matches. The total number of matches will be 994 + 3 + 2 = 999.

Now, You can generalize it.

Hope that 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.