Sea a un conjunto de 100 números naturales. demostrar que existe un conjunto B $$B\subseteq A$$ tal que la suma de B elementos puede ser dividido por 100
Estoy atrapado por un par de días ahora. Por favor, ayuda!
Respuestas
¿Demasiados anuncios?
tome una cadena de subconjuntos de $A$, $\emptyset\subset\{a_1\}\subset\{a_1,a_2\}\subset...\subset A$. esta cadena tiene 101 elementos. ahora ordenarlos por su suma modulo 100. dos de los conjuntos de la cadena debe ser igual modulo 100. por lo tanto, no es $n>m$ con $ (0+a_1+...+a_n)-(0+a_1+...+a_m) $ divisible por 100, de modo que $a_{m+1}+...+a_n$ es divisible por 100.
aquí está una explicación más detallada:
deje $A_0=\emptyset, A_i=\{a_1,a_2,...,a_i\}$ donde $A=\{a_1,...,a_{100}\}$. deje $s_0=0, s_i=\sum_{k=1}^ia_k$. tenemos 101 números de $s_0,...,s_{100}$ que vamos a resolver en 100 grupos de $G_0,...,G_{99}$. ponemos a $s_i$ en el grupo $G_r$ si el resto después de dividir $s_i$ $100$ es igual a $r$. ya hay 101 números de $s_i$ y sólo el $100$ grupos, uno de los grupos de $G_r$ tienen por lo menos dos números de $s_n,s_m$ (sin pérdida de generalidad, $n>m$ puesto que uno de ellos tendrá mayor subíndice). si $s_n=100k+r$ $s_m=100l+r$ $s_n-s_m=100(k-l)$ es divisible por $100$. por construcción, el número de $s_n-s_m$ es precisamente la suma de $a_{m+1}+...+a_n$ correspondiente al subconjunto $A_n\backslash A_m$ $A$ (tenga en cuenta que $A_n$ no está vacía, debido a que $n>m\geq0$ y $A_m$ es un subconjunto de a$A_n$, de modo que la diferencia de $A_n\backslash A_m$ es no vacío).
Pokus
Puntos
1809
El uso de la inducción con la declaración de ser "un subconjunto de cada número menor o igual que n, entonces a mirar los números mod 100. Añadir el nuevo número a un subconjunto apropiado de la misma mod 100 (aquí es donde el principio del palomar viene). Para la inducción de la raíz mirada en los casos de los números pares e impares (1 y 2).
