Aplicación del principio de orificio de Paloma

Question

Hay un problema en mi libro de texto que estoy teniendo dificultades para comprender. La solución dada omite los pasos y es difícil de descifrar. El problema es el siguiente:

"Durante un mes con 30 días, un equipo de béisbol juega al menos una partida de un día, pero no más de 45 juegos. Demostrar que debe haber un período de cierto número de días consecutivos durante el cual el equipo debe jugar exactamente 14 juegos."

No sé cómo llegar a la conclusión de 14 juegos. Alguien que me pueda ayudar a entender esta aplicación de la paloma-agujero principio se agradecería mucho, gracias.

Answer 1

Deje $\{a_i\}_{i = 0}^{30}$ denotar el número de juegos hasta e incluyendo el $i$-ésimo día del mes (put $a_0 = 0$). Dadas las condiciones de la tarea, $\{a_i\}$ es un aumento de la secuencia con todos los miembros distintos y $0 \leq a_i \leq 45$.

Ahora, considere la secuencia de $\{a_i + 14\}_{i = 1}^{30}$ (agregar $14$ a cada miembro de la secuencia original). También es creciente con todos los miembros distintos, pero con $14 \leq a_i + 14 \leq 59$. Junto a estas secuencias consisten $62$ enteros entre $0$$59$, por lo que por el principio del palomar, dos de ellos debe ser igual.

Dado que tanto las secuencias de $\{a_i\}$ $\{a_i + 14\}$ tienen distintos miembros, debe ser índices de $j$ $k$ $j \ne k$ tal que $a_j = a_k + 14$. Esto significa que de los 14 partidos fueron jugados en el período comprendido entre el $(k + 1)$-st y el $j$-ésimo día.

Answer 2

Deje $f(n)$ el número de juegos jugados en la primera $n$ días. Entonces sabemos que $f(0)=0$, $f(30)\le 45$ y $f(k+1)\ge f(k)+1$$0\le k<30$. Si podemos encontrar la $0\le i<j\le 30$$f(j)=f(i)+14$, esto significa que en los días $i+1,\ldots, j$ total $14$ los juegos son jugados y hemos terminado.

Deje $g(k)$ del resto de $f(k)$ modulo $14$. A continuación, una de las $14$ posibles valores deben ocurrir al menos $3$ veces debido a $2\cdot 14<31$. Así que hay números de $0\le a<b<c\le 30$$g(a)=g(b)=g(c)$. A continuación, $f(b)-f(a)$ $f(c)-f(b)$ ambos son múltiplos de $14$ y son ambos positivos. Si ninguno de ellos es igual a $14$,$f(c)-f(b)\ge 28$$f(b)-f(a)\ge 28$, de modo que $f(c)\ge 56+f(a)\ge56$, lo cual es absurdo. Llegamos a la conclusión de que $f(b)-f(a)=14$ o $f(c)-f(b)=14$ (o ambos).

Comentario: El problema no es "apretado" en el siguiente sentido: La solución anterior, también funciona si permitimos a a $55$ juegos durante el mes; o, alternativamente, si reemplazamos $14$ con cualquier número de $\in\{12,\ldots,15\}$.

Answer 3

Para $k=0$ a través de $30$ deje $g_k$ el número total de juegos jugados hasta el medio día $k$. Entonces

$$0=g_0<g_1<g_2<\ldots<g_{30}\le 45\;.$$

Ahora vamos a $h_k=g_k+14$$k=0,\ldots,29$, por lo que

$$14=h_0<h_1<h_2<\ldots<h_{29}=g_{29}+14<g_{30}+14\le 45+14=49\;.$$

Tenga en cuenta que $g_1\ge 1$, e $h_{29}\le 48$.

Si podemos encontrar la $k$ $\ell$ tal que $h_k=g_\ell$, estamos en el negocio porque, a continuación,$g_k+14=g_\ell$, lo que significa que $14$ juegos se juegan en días $k+1$ a través de $\ell$.

Hay $30$ diferentes números de $h_0,\ldots,h_{29}$, todas situadas en el rango de $14$ a través de $48$ inclusive, y $30$ diferentes números de $g_1,\ldots,g_{30}$, todas situadas en el rango de $1$ a través de $45$ incluido. En total, entonces, tenemos $60$ números en el rango de $1$ a través de $48$, y el principio del palomar asegura que al menos dos de ellos deben ser de la misma. Los números de $h_k$ son todos distintos, y los números de $g_\ell$ son distintos, por lo que algunos $h_k$ debe ser igual a algunos $g_\ell$: $k$ $\ell$ tal que $h_k=g_\ell$.