Problema del maestro de ajedrez

Question

Desde Introducción a la combinatoria por Richard Brualdi

Tenemos un maestro de ajedrez. Tiene 11 semanas para preparar una competición, así que decide que practicará todos los días jugando al menos una partida al día. Para asegurarse de que puede tomarse un par de descansos, también decide que no jugará más de 12 partidas a la semana.

Mi pregunta es, ¿cómo probar/desprobar que habrá una sucesión de días (consecutivos) en los que jugará k juegos, $k \geq 22$ ?

En concreto, no entiendo muy bien el uso del principio de encasillamiento aquí.

¡Gracias de antemano! :D

EDITAR

Intentaré aclarar lo que pregunto:

El objetivo es demostrar que para todos los horarios de práctica posibles que hace el maestro de ajedrez, habrá siempre sea una secuencia consecutiva de días tal que juegue exactamente k juegos.

Así, por ejemplo, si k \= 22 años, ¿cómo se demuestra que, independientemente de su horario, va a siempre jugar exactamente k juegos en r días, $1 \leq r\leq 77$ .

Mi pregunta principal es: ¿cuál es el método general para probar diferentes valores de k ? ¿Hay valores de k (de 1 a 132 inclusive) que son imposibles de obtener?

Tenga en cuenta que no necesariamente tiene que jugar 132 partidos en 77 días. Además, hay que tener en cuenta los límites de k .

Answer 1

Para $\displaystyle 1 \le k \le 24$ definitivamente puedes demostrar que el maestro debe haber jugado exactamente $k$ juegos en algún conjunto de días consecutivos, utilizando el principio de encasillamiento.

Supongamos que el número total de juegos que el maestro ha jugado hasta el final del día $\displaystyle j$ es $\displaystyle g_j$ .

Ahora considere el $\displaystyle 154$ números: $\displaystyle g_1, g_2, \dots, g_{77}, g_1 + k, g_2 + k, \dots, g_{77} + k$

Se trata de un conjunto de $\displaystyle 154$ números entre $\displaystyle 1$ y $\displaystyle 132+k$ .

Para $\displaystyle k \lt 22$ dos de ellos deben ser iguales. Como $\displaystyle g_i \neq g_j$ (al menos un juego al día) debemos tener eso $\displaystyle g_j + k = g_i$ para algunos $\displaystyle i,j$ .

Para $\displaystyle k=22$ debemos tener que los números son $\displaystyle 1,2, \dots, 154$ en cuyo caso, la primera (y la última) $\displaystyle 22$ días, el maestro debe haber jugado $\displaystyle 1$ juego todos los días.

Para $\displaystyle k=23$ podemos suponer que $\displaystyle g_i \neq 23$ y como $g_i \ge 1$ tenemos $g_i + k \neq 23$ .

Así, por un argumento similar al anterior, debemos tener $\displaystyle 154$ números que toman todos los valores en $\displaystyle 1, 2, \dots, 155$ , excepto $\displaystyle 23$ y el maestro debe haber jugado $\displaystyle 1$ juego cada uno de los últimos $\displaystyle 23$ días.

Para $\displaystyle k=24$ , se puede demostrar que el maestro debe haber jugado $\displaystyle 1$ juego la primera $\displaystyle 23$ días (después de eliminar uno de los números en $\displaystyle 133, 134 \dots$ ), y luego un gran número de juegos el siguiente, violando el $\displaystyle 12$ restricción de juegos por semana (aquí es donde realmente usamos esa restricción para un específico semana).

Podríamos utilizar este tipo de argumento para demostrar que $\displaystyle k$ cerca de $\displaystyle 24$ pero para los más grandes $\displaystyle k$ Supongo que se puede encontrar un conjunto de juegos que no lo hagan (tal vez una búsqueda en el ordenador ayude a ello).

Answer 2

Tiene $11$ semanas de formación (o $77$ días). El número mínimo y máximo de partidos para este periodo es $77$ y $11 \cdot 12=132$ respectivamente.

Tenemos situaciones distintas:

1) En cualquier periodo de $k$ días consecutivos que juega al menos $k$ juegos. Como bien has preguntado.

2) El período más pequeño de $n$ días como para que juegue $k=22$ juegos ocurren cuando considera una semana con un número máximo de juegos $12$ más días después y antes de esta semana con un número máximo posible de partidos. Observe que en un día es posible jugar $6$ juegos. Así que, tómate un día con $4$ juegos, una semana con $12$ juegos, y un día más con $6$ juegos. A continuación, se obtiene $22$ juegos en $9$ días.

Utilizando 1) y 2) concluimos que entre $9$ y $k$ días siempre podemos hacer la elección de $22$ juegos.

¡Supongo que es muy útil!