Una aplicación de encasillar Principio

Question

Demostrar que a partir de cualquier conjunto de $11$ números naturales, existe 6 números tales que su suma es divisible por $6$.

Answer 1

Lema. De cualquier conjunto de cinco números naturales podemos elegir tres, de tal manera que su suma es múltiplo de $3$.

Prueba: Si tres de los números que tienen el mismo resto $\pmod 3$, su suma es múltiplo de $3$ y hemos terminado. Por lo tanto asumir cada resto se produce más de dos veces, por lo que - por el pigeon-hole principio de cada resto se produce al menos una vez. Pero $0+1+2\equiv 0\pmod 3$. $_\square$

Por el lema, elige tres números de $a_1,a_2,a_3$$3\mid a_1+a_2+a_3$. Forma el resto de $8$ números de pick $b_1,b_2,b_3$$3\mid b_1+b_2+b_3$. Froim el resto de los cinco números de pick $c_1,c_2,c_3$$3\mid c_1+c_2+c_3$. Entre los tres números $a_1+a_2+a_3$, $b_1+b_2+b_3$, $c_1+c_2+c_3$, los dos deben tener la misma paridad (de nuevo por el pigeon-hole principio). Juntos podemos obtener seis números cuya suma es divisible por tanto $3$$2$, por lo tanto, por $6$.