16
$\begingroup$

$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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
38
$\begingroup$

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

Improve this answer
$\endgroup$
14
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 6
    $\begingroup$ You overthought it a bit... $\endgroup$
    – Deusovi ♦
    Feb 22, 2016 at 1:06
  • $\begingroup$ @Deusovi Right, your solution is much much simpler and more elegant. $\endgroup$
    – Fimpellizzeri
    Feb 22, 2016 at 1:37
  • $\begingroup$ Yes but I would argue that this is the proper math going through calculating how many games for a tree tournament. $\endgroup$
    – Patrick Roberts
    Feb 22, 2016 at 14:54
  • $\begingroup$ 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 $\endgroup$
    – Kevin
    Feb 22, 2016 at 19:40
1
$\begingroup$

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. :)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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