Dado cualquier nueve número, demostrar que existe un subconjunto de cinco números tales que su suma es divisible por $5$.
He intentado tomar los números en el formato de $5k+1$, $5l+2$ y así sucesivamente. Sin embargo, estoy atrapado en la elección de CUALQUIER cinco de ellos... Además, los números incluidos en el subgrupo puede o no puede pertenecer al mismo formato.
Podemos probar el siguiente más resultado general, que es un problema clásico. La prueba a continuación es un clásico.
Lema Si $p$ es primo, entonces entre cualquiera de las $2p-1$ números a los que usted puede encontrar $p$ cuya suma es divisible por $p$.
Prueba: Vamos a $a_1,.., a_{2p-1}$ los números.
Considerar todos los $n=\binom{2p-1}{p}$ subconjuntos de a $p$ números y denotan por $S_1,...,S_n$ de las sumas de cada subconjunto.
Vamos $$S:= S_1^{p-1}+...+S_n^{p-1}$$
Observemos primero que $p|S$.
Tenga en cuenta que $$S_j^{p-1} = (a_{j_1}+...+a_{j_p})^{p-1}$$ Cualquier término de esta suma tiene la forma $a_{k_1}^{b_1}a_{k_2}^{b_2}...a_{k_l}^{b_l}$ con un coeficiente de ser $\binom{p-1}{b_1,..,b_k}$. Por lo tanto, $S$ es la suma de los términos de este formulario.
Ahora, veamos el coeficiente de un término. Siempre cuando este aparece en algunos $S_j^{p-1}$ el coeficiente es exactamente $\binom{p-1}{b_1,..,b_l}$. Así que tenemos que entender cómo muchas veces hace que esta aparezca en $S_j^{p-1}$. En orden para que esto suceda, $a_1,a_2,..., a_l$ necesitan ser $l$ de la $p-1$ términos, el otro $p-l$ puede ser cualquier cosa. Por lo tanto, esta aparece en exactamente $\binom{2p-1-l}{p-l}$ sumas. Pero desde $p$ es primo, $$p| \frac{(2p-1-l)!}{(p-l)!(p-1)!}=\binom{2p-1-l}{p-l}$$
Ahora, si suponemos por la contradicción que ninguno de $S_j$ es divisible por $p$, por Fermat Poco Teorema tenemos $$S= S_1^{p-1}+...+S_n^{p-1} \equiv 1+1+...+1 \equiv n \pmod{p}$$
Pero $n \not\equiv 0 \pmod{p}$ contradicción.
Ponerlos en cinco subconjuntos de acuerdo a sus resto mod 5. Usted tiene [0],[1],[2],[3],[4].
Si todos los cinco subconjuntos de contener un número, tome uno de cada subconjunto.
Si sólo cuatro subconjuntos de contener un número, entonces uno contiene al menos tres. Supongamos que [a] contiene tres o más, [b] no contiene ninguno. Tomar tres de [a], ninguno de [b],ninguno de [2a-b], y uno de cada uno de los otros dos. (Imaginen que empezar con uno de cada grupo, pero reemplace [b] y [2a-b] por dos extra [a], la suma (mod 5) sigue siendo el mismo.)
Si uno o dos subconjuntos contener un número, tomar de cinco a partir de un subconjunto.
Supongamos que tres subconjuntos de [a],[b],[c] contienen un número, pero no [d] o [e]. Dibujar un pentágono regular con [0],[1],[2],[3],[4] en fin, en las esquinas. Por simetría, se puede etiquetar a,b,c de modo que [d+e]=[a+b]=[2c]. Si es posible, elija un+a+b+b+c, o a+b+c+c+c. Si esto es imposible, entonces sólo hay uno en el [a], y también menos de tres en [c]. Así que hay al menos seis en [b], y usted tiene que elegir cinco de [b].
Es solo una idea, aún no finalizado.
$c_0$ - conteo de números con resto 0 mod 5
$c_1$ - conteo de números con resto 1 mod 5
$c_2$ - conteo de números con resto 2 mod 5
$c_3$ - conteo de números con el resto 3 mod 5
$c_4$ - conteo de números con el resto 4 mod 5
Es claro que $c_k < 5$ todos los $k$ (si no es cierto, vamos a escoger los 5 números con el mismo residuo y el problema está resuelto).
También es claro que al menos uno de $c_k$ es cero (si no vamos a elegir 1 número de cada residuo y se resuelve el problema).
El uso de estas dos observaciones, mira todos los casos posibles, acerca de que $c_k$ es exactamente cero. Vea si usted puede elegir 5 números de los otros que conseguir el trabajo hecho.
... déjame que piense más si podemos cortar más de la lógica de ramas ...
Esto se puede solucionar usando principio del casillero. Aquí está una idea:
Se pueden agrupar los pares de números que terminan en dígitos diferentes como $(1,4),(2,3),(3,2),(4,1)$ ahora cada vez que usted escoge 5 números al azar, es gurranteed que cualquier un par mas muy recogido (principio del casillero) $\implies$ el número termina en 5 $\implies$ divisible por 5.
Tenga en cuenta es solo una idea, voy a intentar en el lenguaje más matemático.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
