Problema de combinatoria (principio del casillero).

Question

dejado {${a_i}$} $1\le i \le 55$ ser una secuencia de enteros positivos (no 0) y $\sum_{i=1}^{55}a_i \lt 95$.

Y me pide para demostrar que debe existir una secuencia $k \lt l$ $[55]$, que $\sum_{i=k+1}^{l}a_i = 15$.

Pensé en esto: Si la secuencia es 1 así que, aquí, el mosto existen uno, ina del caso que no todos ellos 1, todos ellos no pueden ser 2, por lo que la suma de la secuencia es a delimitarse por 55 y 94, solo siento que se pretendía utilizar el principio del casillero y no puedo averiguar cómo.

Answer 1

Considere la secuencia inicial de sumas $S(0),S(1),\ldots,S(55)$ $$ S(n)=\sum_{i=0}^na_i. $$ Tenemos $$S(0)=0<S(1)<S(2)<\cdots<S(55)<95,$$ una secuencia de 56 distintas enteros en el intervalo de $[0,94]$ $95$ posibilidades.

Tenga en cuenta también el número de secuencia $T(i)=S(i)-15$. Hay 56 de ellos, todos los números enteros en el rango de $[-15,79]$. Porque todos son distintos, al menos $56-15=41$ de ellos son no-negativos.

Sugerencias:

• Se puede demostrar que los conjuntos de $\{S(i)\mid 0\le i<56\}$ $\{T(i)\mid 0\le i<56\}$ debe tener un no-vacío intersección?
• ¿Ves cómo la demanda sigue de esto?

Spoiler #1

Entre ellos, los dos conjuntos tienen 97 enteros positivos en el rango de $[0,94]$ por lo que el principio del palomar nos dice que hay cierta superposición.

Spoiler #2

Si $T(\ell)=S(\ell)-15=S(k)$ $$ \sum_{i=k+1}^\ell a_i=S(\ell)-S(k)=15.$$

Answer 2

Esta es esencialmente la misma respuesta, como ya se ha dado, pero desde un punto de vista ligeramente diferente. Mantener este truco, ya que aparece por todo el lugar, por ejemplo, en la prueba de la Desigualdad de Chebyshev.

En lugar de escribir $$ S = \sum_{i=1}^{55} a_i $$ donde $a_i \in \{1, 2, 3, \cdots\}$, vamos a $N_k$ el número de $i \in \{1, \cdots, 55\}$ tal que $a_i = k$ y escribir $$ S = \sum_{k=1}^\infty k \cdot N_k. $$ Es decir, el grupo de la $a_i$ en valor y sume los totales de cada grupo. Dentro de un grupo, cada elemento tiene el mismo valor, de modo que sólo necesita contar los elementos. Si estás familiarizado con la teoría de la medida, esto es, esencialmente, la conversión de una integral de Riemann en una integral de Lebesgue. (Por el contrario, si la teoría de la medida es confuso, pensando en ello de esta manera puede ayudar.)

Ahora observe que para cualquier $a_i > 1$, estamos añadiendo al menos $2$ a la suma, por lo que nos puede aproximar como este: \begin{align} S &= N_1 + \sum_{k=2}^\infty k \cdot N_k \\ &\ge N_1 + 2 \cdot \sum_{k=2}^\infty N_k \\ &= N_1 + 2 \cdot (55 - N_1) \\ &= 110 - N_1. \end{align}

A partir de aquí, utilice el hecho de que $S < 95$ a mostrar que hay un gran número de $a_i$$a_i = 1$.