Nacional 2023 N3 P6

[Felibauk]

En un torneo de ping pong participan $n \geq 3$ jugadores que llamaremos $1,2, \dots, n$. Las reglas del torneo son las siguientes: al comienzo, los jugadores están en una fila, ordenados de $1$ a $n$. Los jugadores $1$ y $2$ juegan el primer partido. El ganador queda al comienzo de la fila y el perdedor se coloca detrás del último de la fila. En la siguiente jugada, se enfrentan los dos que en ese momento son los primeros dos de la fila, el ganador queda primero en la fila y el perdedor va al final de la fila, justo detrás del último perdedor. Y así siguiendo. Al cabo de $N$ partidos, el torneo finaliza. El jugador $1$ ha ganado $a_1$ partidos, el jugador $2$ ha ganado $a_2$, y así siguiendo hasta el jugador $n$, que ha ganado $a_n$ partidos (es obvio que $a_1+a_2+ \dots + a_n=N$). Determinar cuántos partidos ha perdido cada jugador, en función de $a_1,a_2, \dots, a_n$.

[Danielito2435]

@Gianni De Rico ... Puedes publicar la solución de este??

[Ignacio Daniele]

Spoiler: mostrar

$N=a_i+p_i+p_i(n-2)+b(i)-f(i)$
$b(i)=i-2$ si $i≠1$, si $i=1; b(i)=0$ (es decir, está relacionado con la posición en la que inicia).
$f(i)$ tiene una definición muy similar, solo que con respecto a la posición en la que finaliza, pudiendo valer entre $0$ y $n-2$
$p_i(n-1)=N-a_i-b(i)+f(i)$
$p_i=\frac{N-a_i-b(i)+f(i)}{n-1}$
$p_i$ es entero, entonces $N-a_i-b(i)+f(i)$ es múltiplo de $n-1$
Como $0\leq f(i)\leq n-2$, solo hay un valor que cumple de $f(i)$, que es el único que me permite que el resultado sea entero, y es no negativo, en definitiva, estoy redondeado para arriba $\frac{N-a_i-b(i)}{n-1}$.
En conclusión:
$p_i=techo[\frac{N-a_i-b(i)}{n-1}]$

[usuario250]

Algunas ideas

Spoiler: mostrar

La idea es separar a los N partidos en conjuntos de (n - 1) partidos consecutivos y r partidos finales (con r < (n - 1)).
Cada uno de ese conjunto de (n - 1) partidos consecutivos, se puede pensar como un torneo.
El "campeón" de cada torneo es el que gana el último partido del torneo.
El estado inicial de cada jugador es el número de partido (de 1 a (n - 1)) dentro del torneo en el que el jugador juega su primer partido. (Hay 2 jugadores con estado inicial 1, 1 con estado inicial 2,...,1 con estado inicial (n - 1))
El estado final de cada jugador es el número de partido (de 1 a (n - 1)) dentro del torneo SIGUIENTE en el que el jugador jugará su primer partido. (Hay 2 jugadores con estado final 1, 1 con estado final 2,...,1 con estado final (n - 1))

NOTA: si bien no tienen los subíndices correspondientes, a partir de acá, f,g,i son respectivos a cada jugador.

En cada torneo:
Salvo el campeón (que no pierde ningún partido en el torneo), el resto pierde exactamente un partido.
El campeón gana g = (n - i) partidos en el torneo, donde i es su estado inicial.
Estado final de cada jugador:
Para el campeón: f = 1 = 1 + g - g = 1 + g - (n - i) = 1 + g + i - n = g + i - (n - 1) (f es el estado final, i el estado inicial y g la cantidad de partidos ganados en el torneo)
Para el resto: f = g + i (esto es porque cuando un jugador pierde, recién vuelve a jugar en (n - 1) partidos)

Para los r partidos finales:
El estado inicial es el estado final del último torneo
El estado final es:
f = 1 para el que pierde el 1er partido,
...
f = r para el que pierde el r-ésimo partido
f = r + 1 para el que gana el r-ésimo partido
---------
f = i (siendo i el estado inicial) para i > r

Luego, en los r partidos finales,
Hay 2 jugadores que terminan con f = (r + 1) y 1 jugador que termina con f = e (para cada e entre 1 y (n - 1) a excepción de (r + 1))
Los que terminan con f <= r perdieron un partido
Los que terminan con f > r no perdieron ningún partido
f = g + i, siendo g la cantidad de partidos que ganó el jugador en estos r partidos finales.

Ahora, viendo los N partidos:
En cada jugador, el estado final es (i + g) mod (n - 1)
La cantidad de torneos en la que cada jugador sale campeón es la parte entera de (i + g)/(n - 1)
En los torneos de (n - 1) partidos (la cantidad de torneos es (N - r)/(n - 1)), cada jugador pierde 1 partido por cada torneo que no sale campeón y 0 partidos por cada torneo en que sale campeón.
En los r partidos restantes, los jugadores con estado final f > r no pierden ningún partido y los jugadores con estado final f <= r pierden 1 partido.