Demuestra que para toda pareja de enteros positivos $n$ y $m$ con $n \geq m$ se cumple que:
Para cualquier conjunto de $n$ enteros se tiene que existen por lo menos $2^{n-m+1}$ subconjuntos que su suma es $0$ $mod$ $m$. (El conjunto vacío cuenta como uno con suma congruente a $0$ $mod$ $m$)
jueves, 26 de mayo de 2016
Suscribirse a:
Comentarios de la entrada (Atom)
3 comentarios:
Sea $S$ el conjunto de los $n$ enteros. Para un conjunto $T \subseteq S$ denotemos por $R(T)$ el conjunto de todos los residuos que dejan las sumas de los elementos de los subconjuntos de $T \pmod m$. Digamos que un subconjunto $T$ de $S$ con a lo más $m - 1$ elementos es bueno si $\vert R(T) \vert \geq \vert T \vert + 1$. Consideremos un conjunto $A$ que tiene la máxima cardinalidad posible de entre los conjuntos buenos (posiblemente $A = \varnothing$).
Sea $B = S \setminus A = \{b_1, b_2, \dots, b_l\}$. La maximalidad de $A$ implica que si $s \in R(A)$, entonces $s + b_i \in R(A)$ para todo $i$ (consideramos estos números módulo $m$). Inductivamente se sigue que $s + kb_i \in R(A)$ para todo entero positivo $k$, y en particular $(m - 1)b_i \in R(A) \implies -b_i \in R(A)$. Luego, para cada $T \subseteq \{1, 2, \dots, l\}$ tenemos que
$$- \sum_{t \in T} b_t \in R(A)$$
Esto implica que para todo $Y \subseteq B$ existe un conjunto $X \subseteq A$ tal que $S(X) \equiv -S(Y) \pmod{m}$ (donde $S(T)$ denota la suma de los elementos de un conjunto $T$), y entonces $S(X \cup Y) \equiv 0 \pmod{m}$. Se sigue que hay al menos $$2^{n - \vert A \vert} \geq 2^{n - m + 1}$$ subconjuntos de $S$ que cumplen lo deseado (uno por cada subconjunto de $B$).
Publicar un comentario