1
$\begingroup$

This question already has an answer here:

We are organizing a tennis tournament. The rules are the default ones.

  • 2 players play against each other
  • the winner advances to the next round
  • this goes on until one player is crowned champion.

1000 players signed up for the tournament.
How many matches will our tournament have?
(please provide an explanation for the number you find)

Bonus (my appreciation): how many matches will there be for $n$ players?

$\endgroup$

marked as duplicate by Deusovi, Community Apr 19 '16 at 14:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

In every game that will be played, there is one loser. Because you need $1$ champion (and $999$ losers), you need

999 games. More general, for any tournament with $n$ players, you need $n-1$ games.

$\endgroup$
2
$\begingroup$

The answer is 999.
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'.

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

Ex- 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$
  • $\begingroup$ but what if N is not $2^k$ ? $\endgroup$ – Marius Apr 19 '16 at 14:36
  • $\begingroup$ Sorry for poor formating. I am new here. You can always break any number in sum of powers of two. Like For 1000, I can write 1000 = 512 + 256 + 128 + 64 + 32 + 8. Now, 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. Similarly, For 3 people, there will be 2 more matches. Hence, The total matches will be 999. $\endgroup$ – Gautam Kumar Apr 19 '16 at 14:38

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