There´s a ping pong tournament with $n\geq 3$ participants that we´ll call $1, 2, \dots n$. The tournament rules are the following ones: at the start, all the players form a line, ordered from $1$ to $n$. Players $1$ and $2$ play the first match. The winner is at the beginning of the line and the loser is placed behind the last person in the line.In the next play, the two who at that moment are the first two in line face each other, the winner is first in line and the loser goes to the end of the line, just behind the last loser. And so on. After $N$ matches, the tournament ends.Player number $1$ won $a_1$ matches, player number $2$ won $a_2$, and so on till player $n$, that has won $a_n$ matches (it is trivial that $a_1+a_2+\dots+a_n=N)$.Determine how many games each player has lost, based on $a_1, a_2, \dots , a_n$
Problem
Source: Argentina MO 2023 Level 3 P6
Tags: number theory
13.05.2024 11:20
Interesting. Let $b_i$ be the number of matches lost by $i$. We count the position of the players from the back of the line: so initially, player $n$ has position $1$, $n-1$ has position $2$, and so on. Also, since there is no functional difference between the first two places, both of these are counted as position $n-1$. Let $g(i)$ denote the initial position of $i$. Thus $g(1)=n-1$ and $g(i)=n+1-i$ for $2 \leq i \leq n$. Let $f(i)$ denote the final position of $i$, which is unknown. After every loss, the player has to move $n-1$ spots before being able to play a match again. Initially, the player has to move $n-1-g(i)$ spots to get to their first match, and at the end, they have to move $f(i)$ spots to end up where they are. A change in position occurs iff a match is played. Thus, the total number of matches is $$N=(n-1-g(i))+a_i+(b_i-1)(n-1)+f(i)=a_i-g(i)+b_i(n-1)+f(i).$$Note that $1 \leq f(i) \leq n-1$ for all $i$; thus $$b_i+\frac{f(i)-1}{n-1}=\frac{N+g(i)-a_i-1}{n-1}$$$$\implies b_i = \left \lfloor \frac{N+g(i)-a_i-1}{n-1} \right \rfloor.$$Thus putting the expression for $g(i)$ back, we get $$\boxed{b_1=\left \lfloor \frac{N+n-a_1-2}{n-1} \right \rfloor} \ \text{ and } \ \boxed{b_i=\left \lfloor \frac{N+n-a_i-i}{n-1} \right \rfloor \text{ for } \ 2 \leq i \leq n}.$$Interestingly, $b_i$ only depends on $N,n,a_i$.