Conjuntos

Buster

Demuestre que:

\forall A\subset \mathbb{N},\sharp A=2^{n+1}-1,\exists B\subseteq A,\sharp B=2^n:\left(2^n\mid\displaystyle\sum_{x\in B} x\right)

impure

La solución por inducción es bastante standard aunque no por eso fea... tu tienes una solución mas constructiva o por palomar? me pase arto rato tratando de buscar una asi, pero con el animo de ordenar el foro respondere igual.

impure

Solución:
[hide]Razonemos por inducción.
Para n=1 tenemos un conjunto A de 3 elementos, 2 de ellos tendran la misma paridad, digamos que estos 2 elementos son el subconjunto B, su suma sera divisible por 2.
Asumamos que para algun natural n \ge 1 se cumple el enunciado.
Consideremos ahora n+1, asi que A tiene 2^{n+2}-1 elementos, consideremos dos subconjuntos disjuntos B_1 y B_2, ambos de 2^{n+1}-1 elementos, por lo que quedara un elemento a \in A sin asignar.
Por hipotesis inductiva B_1 y B_2 tienen un subconjunto B_1' y B_2' respectivamente, de 2 ^n elementos cada uno y de suma divisible por 2^n. Consideremos 2^nX y 2^nY la suma de los elementos de B_1' y B_2' respecitvamente, consideremos el conjunto B_1' \cup B_2' que tendra 2^{n+1} elementos y la suma de sus elementos sera 2^n(X+Y), si X e Y tienen la misma paridad entonces B=B_1' \cup B_2'. En caso contrario consideremos los conjuntos B_1 / B_1' y B_2/B_2', ambos de 2^{n+1}-1-2^n=2^n-1 elementos y consideremos el conjunto (B_1 / B_1') \cup (B_2 / B_2') \cup \{a\} que tendra 2^n-1+2^n-1+1=2^{n+1}-1 elementos que por hipotesis inductiva posee un subconjunto B_3 de 2^n elementos y de suma divisible por 2^n, digamos que su suma es 2^nZ. Ahora Z tendra la paridad de X o de Y, sin perdida de generalidad digamos que tiene la paridad de X, asi que consideremos B=B_3 \cup B_1' y se termina la inducción.[/hide]