[iNuGaM]

Hola, tengo que resolver el siguiente ejercicio por medio del principio del palomar pero no sé por dónde podría encararlo ...

Muestre que en un conjunto cualquiera de 21 números enteros positivos, existe un subconjunto de 5 números cuya suma es divisible por 5. Ayuda: probar que hay un subconjunto de al menos 5 números cuyo resto al dividir por 5 coincide.

Entiendo que los posibles restos de dividir a algún número por 5 son 0, 1, 2, 3 y 4, pero no sé cómo podría aplicar esto al enunciado.

[Ricardo Boza]

Hola,

Imagina que los números son palomas. A cada número le corresponde un resto. Los restos \( \{0,1,2,3,4\} \) son los cajones. Hay 5.

Si la primera paloma la envías al primero, la segunda al segundo, la tercera al tercero... y vas repitiendo...

Si quieres averiguar cuántas palomas corresponden por cajón: 21/5, caben a 4 palomas por cajón, pero sobra una, que debe ir a alguno de los cajones.

Entonces ya lo tienes.

[iNuGaM]

Gracias!

[guillem_dlc]

Buenas iNuGaM,

Sea \( q\in \mathbb{Z}^+ \) dado. Para cada \( q \), existe algún \( x\in \mathbb{Z}^+ \) y algún \( v\in \{ 0,1,2,3,4\} \) tal que \( q=5x+v \) por el algoritmo de la división.

Ahora sea \( A=\{ q_i\in \mathbb{Z}^+: 1\leq i\leq 21\} \subset \mathbb{Z}^+ \). Entonces para cada \( q_i \), existe \( x_i\in \mathbb{Z}^+ \) y \( v_i\in \{ 0,1,2,3,4\} \) tal que \( q_i=5x_i+v_i \) para todo \( i \). Queremos probar que para cada conjunto \( A \) dado, existe un subconjunto \( B \) de \( 5 \) números tal que su suma es divisible por \( 5 \).

Separamos nuestra demostración en dos casos:

• Si existen cinco \( v_i \) tales que son iguales, sin pérdida de generalidad, podemos suponer que estos son \( v_1, \ldots ,v_5 \) y \( v_1=\cdots =v_5=v \) Entonces tenemos que \( \sum_{i=1}^5 q_i=\sum_{i=1}^5 (5x_i+v_i)=\sum_{i=1}^5 (5x_i+v)=5(x_1+\cdots +x_5)+5v=5(x_1+\cdots +x_5+v) \), de donde vemos que claramente \( q_1+\cdots +q_5 \) es divisible por \( 5 \) y tomando el conjunto \( B=\{ q_i\in \mathbb{Z}^+: 1\leq q_i\leq 5\} \subset A \), tenemos lo que necesitamos.
• Por otra parte, si no existen cinco \( v_i \) que sean todos iguales, por el principio del palomar, tenemos que debe existir como mínimo un \( v_i \) que sea igual a \( 0 \), otro \( v_j \) que sea igual a \( 1 \) y así sucesivamente. Sin pérdida de generalidad, tomamos entonces \( v_1=0 \), \( v_2=1 \), \( v_3=2 \), \( v_4=3 \), \( v_5=4 \). Entonces, tenemos que \( \sum_{i=1}^5 q_i=5(x_1+\cdots +x_5)+(v_1+\cdots +v_5)=5(x_1+\cdots +x_5)+10=5(x_1+\cdots +x_5+2) \), de donde vemos que la suma es divisible por \( 5 \). Por tanto, cogiendo \( B=\{ q_i\in \mathbb{Z}^+: 1\leq q_i\leq 5\} \subset A \), tenemos lo que queremos.

Fijate que el teorema de la división ha sido un resultado muy importante para la demostración. Como ves también hemos utilizado el principio del palomar, como comentaste que era tu intención de ver una aplicación.

Saludos.
[/list]

[Ricardo Boza]

Hola guillem_dlc,

Buenas iNuGaM,

Sea \( q\in \mathbb{Z}^+ \) dado. Para cada \( q \), existe algún \( x\in \mathbb{Z}^+ \) y algún \( v\in \{ 0,1,2,3,4\} \) tal que \( q=5x+v \) por el algoritmo de la división.

Ahora sea \( A=\{ q_i\in \mathbb{Z}^+: 1\leq i\leq 21\} \subset \mathbb{Z}^+ \). Entonces para cada \( q_i \), existe \( x_i\in \mathbb{Z}^+ \) y \( v_i\in \{ 0,1,2,3,4\} \) tal que \( q_i=5x_i+v_i \) para todo \( i \). Queremos probar que para cada conjunto \( A \) dado, existe un subconjunto \( B \) de \( 5 \) números tal que su suma es divisible por \( 5 \).

Separamos nuestra demostración en dos casos:

• Si existen cinco \( v_i \) tales que son iguales, sin pérdida de generalidad, podemos suponer que estos son \( v_1, \ldots ,v_5 \) y \( v_1=\cdots =v_5=v \) Entonces tenemos que \( \sum_{i=1}^5 q_i=\sum_{i=1}^5 (5x_i+v_i)=\sum_{i=1}^5 (5x_i+v)=5(x_1+\cdots +x_5)+5v=5(x_1+\cdots +x_5+v) \), de donde vemos que claramente \( q_1+\cdots +q_5 \) es divisible por \( 5 \) y tomando el conjunto \( B=\{ q_i\in \mathbb{Z}^+: 1\leq q_i\leq 5\} \subset A \), tenemos lo que necesitamos.

Esto está bien porque complementa la segunda parte del ejercicio, que yo no dejé indicada.

• Por otra parte, si no existen cinco \( v_i \) que sean todos iguales, por el principio del palomar, tenemos que debe existir como mínimo un \( v_i \) que sea igual a \( 0 \), otro \( v_j \) que sea igual a \( 1 \) y así sucesivamente. Sin pérdida de generalidad, tomamos entonces \( v_1=0 \), \( v_2=1 \), \( v_3=2 \), \( v_4=3 \), \( v_5=4 \). Entonces, tenemos que \( \sum_{i=1}^5 q_i=5(x_1+\cdots +x_5)+(v_1+\cdots +v_5)=5(x_1+\cdots +x_5)+10=5(x_1+\cdots +x_5+2) \), de donde vemos que la suma es divisible por \( 5 \). Por tanto, cogiendo \( B=\{ q_i\in \mathbb{Z}^+: 1\leq q_i\leq 5\} \subset A \), tenemos lo que queremos.

Esto está mal porque precisamente por el principio del palomar se ha probado que del conjunto \( \{x_i\}_{i\in \mathbb{N}_{21}} \) siempre puede extraerse un subconjunto de 5 elementos \( \{x_j\}_{j\in\mathbb{N}_5} \) tales que si \( x_j=5q_j+r_j \), entonces \( (\forall j\in \mathbb{N}_5)\: r_j=r\in \mathbb{N}_4\cup\{0\} \)

Saludos.

[guillem_dlc]

Correcto! Ya veo, para que sea cierta la segunda parte de mi demostración tendría que quitar lo de "aplicando el principio del palomar". Mi demostración sería sin aplicar el principio del palomar, solo, el algoritmo de la división. Aplicando el principio del palomar, solo es necesario hacer el primer caso que he considerado.

Gracias

Saludos