torneo de piedra, papel o tijera, ganar al menos z veces

Question

Consideremos un torneo de piedra, papel o tijera (uno gana y otro pierde) con n jugadores en el que todos se enfrentan exactamente una vez:

cuál es el número máximo, $z=z(n)$ de partidas que aseguran que al menos un jugador ha ganado z veces?

Lo primero que creo que se necesita es determinar el número de partidos, N, que es $N=\frac{(n-1)n}{2}$ Ahora lo que no sé es cómo calcular cuántos de esos $N$ partidos tienen que jugarse antes de que alguien haya ganado al menos $z$ tiempos.

Answer 1

Tenga en cuenta que si $N \geq n(z-1)+1$ entonces por el principio de Pigeonhole debe haber algún jugador que haya ganado al menos $z$ juegos. De este modo, el establecimiento $z = \lfloor (N-1)/n \rfloor + 1 = \lceil (n-1)/2 \rceil$ es siempre seguro. Para demostrar que esto es lo mejor que podemos hacer, consideremos lo siguiente: todos los jugadores se sientan en un círculo. Para el partido entre el jugador $A$ y el jugador $B$ , dejemos que $A$ gana si y sólo si $B$ está más cerca en $A$ de la derecha que en $A$ de la izquierda. Para los partidos en los que $A$ y $B$ están directamente frente a frente, ya sea $A$ ou $B$ puede ganar (esto sólo ocurre cuando $n$ es uniforme). Si los resultados de los partidos de piedra-papel-tijera siguen este patrón, entonces el número de partidos ganados por cada jugador es fácil de calcular: es $(n-1)/2$ si $n$ es impar, y $n/2$ ou $n/2 - 1$ si $n$ es uniforme. En cualquier caso, cada jugador gana como máximo $z = \lceil (n-1)/2 \rceil$ juegos, por lo que no podríamos haber elegido $z$ para ser más grande.