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?

$\endgroup$
38
$\begingroup$

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

$\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.

$\endgroup$
  • 6
    $\begingroup$ You overthought it a bit... $\endgroup$ – Deusovi Feb 22 '16 at 1:06
  • $\begingroup$ @Deusovi Right, your solution is much much simpler and more elegant. $\endgroup$ – Fimpellizieri Feb 22 '16 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 '16 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 '16 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. :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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