1

N players take part in tennis championship. In every match loser is out. Two players can play a game if in that moment the difference of played games of that two players is not more than 1. They are interested, how many matches will be in the championship (maximal possible number) and what's the maximal possible number of games in which can take part the champion in that case.

Example: n=4, maximum games is 3 and winner plays at maximum 2 matches
n=100 , maximum games is 99 and winner plays at maximum 9 matches

I tried some cases and observed maximum matches are always n-1 but cannot generalize for maximum matches for winner? Is there a way to generalize or formulate for maximum matches played by winner?

savvi singh
  • 293
  • Do you want to require that whenever possible, we make a match between two people with the same (lowest) number of matches already played? Otherwise, weird things can happen. Say $N=8$. If 1 beats 2, 1 beats 3, 4 beats 5, and then 1 beats 4. Now 1,6,7,8 are remaining, and 1 has played three matches, while 6,7,8 have played none. Then we need 6,7, and 8 to play, but if, say, 6 beats 7 and then 8 beats 6, 1 and 8 won't be able to play.... That seems like a weird state for our tournament to get into. With that restriction, I'm betting the answer is the ceiling of $\log_{2}(N)$, or close to it. – coolpapa Jun 13 '14 at 19:15
  • there is no such restriction...there is guaranteed one winner and we want to find out maximum matches that winner can be part of subject to given conditions in the question – savvi singh Jun 13 '14 at 19:33

1 Answers1

2

I'm going to assume here that the maximum number of matches played by the winner is monotonic in the total number of players - I haven't thought about a proof, but I believe it. Let $f(n)$ be the minimum number of players necessary so that the maximum number of matches is $n$. So $f(0) = 1$, $f(1) = 2$, $f(2)=3$, $f(3) = 5$. This suggests that $f(n)$ is Fibnoacci.

To prove this, assume that players 1 and 2 play in the last match of the tournament. Then they haven't played before that point, so essentially, 1 and 2 have played two entirely separate tournaments to get to that point. If player 1 wins and has played $n$ games after the last one, the most efficient way to do that (by monotonicity) is if player 1 has played $n-1$ games, and player 2 has played $n-2$ games going into the final game. The minimum number of players needed to make that happen is $f(n-1) + f(n-2)$, which is thus equal to $f(n)$.

So, if we count 1 as the 0th Fibonacci number, 2 as the 1st, etc., then the answer to your original question comes from counting those numbers. Round $n$ down to the closest Fibonacci number less than it. Whatever the index of that Fibonacci number is, that's your answer. So, for example, 100 would round down to 89, which is the 9th Fibonacci number, giving your answer above.

coolpapa
  • 1,030