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