Principio de encasillamiento y secuencias finitas

Question

Supongamos que tenemos $75$ cajas que están etiquetadas de $1$ a $75$ y que en cada caja hay al menos una bola, pero no hay más de $125$ bolas en total. Estoy tratando de encontrar el mayor número $n \in \left\{1,\, \ldots,\, 75 \right\}$ tal que esta afirmación es verdadera: Existe una colección de cajas vecinas que contienen exactamente $n$ bolas juntas. Con cajas vecinas me refiero a que sus etiquetas tienen que ser consecutivas.

Espero que quede claro lo que quiero decir. Podemos reformular la afirmación así: $1 \leq x_i$ , $1 \leq i \leq 75$ y $\sum_{i=1}^{75} x_i \leq 125$ . Entonces hay una secuencia $x_i,\, x_{i+1},\, \ldots,\, x_{i+j}$ tal que $n=x_i + x_{i+1} + \ldots + x_{i+j}$ para algunos $j$ .

El principio de encasillamiento permite una fácil demostración de la afirmación para $n \leq 24$ que no funciona para $n \geq 25$ . He intentado aplicar el siguiente algoritmo para crear contraejemplos sencillos: Para evitar el primer $n$ cajas de contribuir a una colección, necesitamos $n+1$ bolas en el $n$ de la caja. A continuación, hacemos lo mismo con las siguientes casillas, a partir de $n+1$ y así sucesivamente.

El algoritmo sólo funciona para $33 \leq n \leq 49$ . Para los más pequeños $n$ necesitaríamos dos cajas con $n+1$ bolas, pero como tenemos como máximo $125$ bolas en total y cada caja contiene al menos una bola, no hay suficientes bolas de repuesto. Para $50 \leq n \leq 75$ ni siquiera hay suficientes bolas para poner $n+1$ bolas en cualquier caja.

Si el algoritmo que mencioné anteriormente es óptimo, entonces la afirmación es verdadera para todos $n$ , excepto las que se encuentran entre $33$ y $49$ . Pero si eso es cierto, ¿cómo puedo probarlo para $25 \leq n \leq 32$ y $50 \leq n \leq 75$ ?

Answer 1

Bien, aquí hay un relato más completo de cómo aplicar lo que escribió "Bananarama" al problema original. Esa respuesta parece que resuelve $n=25$ y $32\le n\le37$ sin alteraciones. Para $n$ en el medio, recuerde que las casillas finales no pueden estar vacías. Ahora consideramos valores mayores de $n$ .

Declaración. Una secuencia de $n$ enteros contiene un tramo ininterrumpido con una suma divisible por $n$ .

Prueba. Considerar los subconjuntos $\{a_1\},\{a_1,a_2\},...\{a_1,a_2,...,a_n\}$ . Si ninguno tiene una suma divisible por $n$ sus sumas deben caer en $n-1$ clases de residuos; por el principio de encasillamiento, dos deben estar en la misma clase, en cuyo caso podemos eliminar miembros del conjunto menor del mayor para obtener el tramo con suma divisible por $n$ . $\blacksquare$

En el problema original, con $75$ cajas, debe haber un tramo ininterrumpido de cajas con una suma divisible por $75$ .

Pero esa suma debe ser positiva, y no puede ser $150$ o cualquier otro múltiplo mayor. Así que es $75$ .

Esto funcionará sin modificaciones para $63\le n\le75$ .

Ahora considere $51\le n\le62$ . La primera $n$ contienen un tramo con $n$ o $2n$ bolas. Pero si es $2n$ , luego el último $75-n$ las cajas no contienen más de $125-2n$ bolas. Debe haber al menos tantas bolas como cajas, así que $75-n\le125-2n\implies n\le50$ una contradicción.

Answer 2

Mis más sinceras disculpas, he estado aprendiendo alemán durante los últimos años, y por alguna razón esto me ha hecho leer $n$ como "nueve" en mi cabeza a veces, esto me hizo entender mal el problema. De hecho, el nuevo problema es mucho más sencillo de demostrar.

Aplicamos el mismo lema que antes: Si tenemos cajas $\{1,2\dots n\}$ Cada uno de ellos con un mínimo de $1$ mármol, entonces hay una colección de cajas consecutivas con un múltiplo positivo de $n$ número de canicas. considera las colecciones $\{1\},\{1,2\}\dots \{1,2\dots n\}$ si uno de ellos tiene un múltiplo de $n$ canicas entonces hemos terminado, de lo contrario hay $n-1$ conguraciones que las colecciones pueden tomar mod $n$ y por tanto dos tienen la misma congruencia, por lo que la colección de cajas consecutivas formada por las cajas que están en la colección grande pero no en la pequeña nos da una colección de cajas consecutivas con una suma que es un múltiplo positivo de $n$ .

Si tenemos $75$ cajas entonces por el resultado anterior hay una colección de cajas consecutivas que tiene un múltiplo positivo de $75$ número de canicas. Como no hay más que $125$ canicas que múltiples deben ser $75$ y hemos terminado.