Duda de demostración con palomar de divisibilidad de subconjuntos
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.
Había pensando como que la cantidad de subconjuntos de 5 números es (21,5)= 21!/( 5! ×16!)
Y que tengo x1+X2+..+X5= 5×R
Ya que la suma de cada dígito sería múltiplo de 5
Y después no se cómo podría demostrar.
Lo que debemos notar es que los residuos de cualquier número entero positivo pertenece a este conjunto {0,1,2,3,4}, entonces podemos replantear la pregunta de la siguiente forma
- Hay m₁ números con residuo 0 (al ser dividido entre 5)
- Hay m₂ números con residuo 1 (al ser dividido entre 5)
- Hay m₃ números con residuo 2 (al ser dividido entre 5)
- Hay m₄ números con residuo 3 (al ser dividido entre 5)
- Hay m₅ números con residuo 4 (al ser dividido entre 5)
Donde m₁ + m₂ + m₃ + m₄ + m₅ = 21
Lo que se busca es un número tal 0m₁ + 1m₂ + 2m₃ + 3m₄ + 4m₅ = 5k
Entonces tenemos el siguiente sistema de ecuaciones
$$\begin{cases}
m_1+m_2+m_3+m_4+m_5=21\\
m_2+2m_3+3m_4+4m_5=21
\end{cases}$$Cuya solución es
$$\begin{align}&M=(m_1,m_2,m_3,m_4,m_5)\\&\\&M=(21,0,0,0,0)+k(-5,5,0,0,0)+m_3(1,-2,1,0,0)+m_4(2,-3,0,1,0)+m_5(3,-4,0,0,1)\\&\\&\text{En que }k,m_3,m_4,m_5\in \mathbb Z\end{align}$$El hecho que el susodicho sistema de ecuaciones tenga solución sobre los conjuntos de los naturales afirma también que de 21 números naturales (inclusive enteros) podemos elegir 5 de estos cuya suma sea múltiplo de 5.
1 respuesta más de otro experto
Con el tema de los subconjuntos no sé si podés llegar a algo (ya que ese número que te da sigue siendo muy grande), creo que si estás bien encaminado con la segunda parte del
$$\begin{align}&x_1 + x_2 + x_3 + x_4 + x_5 = 5R\\&\text{Pero lo que no podés asumir es que cada }x_i \text{ será múltiplo de 5}\\&\text{Creo que acá tenés que empezar a separar en casos, aunque creo que siguen siendo unos cuantos:}\\&\text{Caso 1 (trivial): todos los números son múltiplos de 5}\\&\text{Caso 2: solo 1 número es múltiplo de 5}\\&\text{En este caso entonces deberías ver que entre los 4 que quedan los puedes sumar de dos en dos y }\\&\text{que ambos serán múltiplos de 5 (acá creo que deberías usar el tema del palomar diciendo que entre }\\&\text{20 números siempre pasará eso, -aunque hay que demostrarlo)}\\&\text{Caso 3: 2 números son múltiplos de 5}\\&etc...\end{align}$$Siento no poder ayudarte más, pero creo que la respuesta es bastante más extensa que las "pistas" que damos en este sitio...