¿Cuántos subconjuntos no vacíos de {1, 2, ..., n} cumplen que la suma de sus elementos es par?

Question

La cuestión en la que estoy trabajando es el caso de $n$ = 9. ¿Cuántos subconjuntos no vacíos de $\{1,2,...,9\}$ tienen que la suma de sus elementos es par?

Mi solución es que la suma de elementos es par si y sólo si el subconjunto contiene un número par de números Impares. Como se trata precisamente de la mitad de los subconjuntos, la respuesta es $\frac{2^{9}}{2}=2^8$ . Entonces la pregunta especifica no vacía por lo que la respuesta final es $2^8-1$ . ¿Es esto correcto? En general supongo que las soluciones son $2^{n}-1$ . Mi problema es ¿por qué exactamente la mitad de los subconjuntos tienen un número par de números Impares? ¿Podemos establecer una biyección entre subconjuntos con número impar de números Impares y número par de números Impares?

Answer 1

Dejemos que $S$ sea un subconjunto de $\{0,1,2,\dots,9\}$ , posiblemente vacía. Tenga en cuenta que $1+2+\cdots +9=45$ . Por tanto, la suma de los elementos de $S$ es par si y sólo si la suma de los elementos del complemento de $S$ es impar.

Dividir los subconjuntos de $\{1,2,\dots,9\}$ en pares complementarios. Hay $2^8$ tales pares, y exactamente un elemento de cada par tiene suma par. Por lo tanto, hay $2^8$ subconjuntos con suma par, y $2^8-1$ si excluimos el conjunto vacío.

Observación: Supongamos que $1+2+\cdots+n$ es impar. Este es el caso cuando $n\equiv 1\pmod{4}$ y cuando $n\equiv 2\pmod{4}$ . Entonces el mismo argumento muestra que hay $2^{n-1}$ subconjuntos con suma par.

Podemos utilizar otro argumento para el caso general. Obsérvese que hay tantos subconjuntos de $\{1,2,\dots,n\}$ que contienen $1$ ya que hay subconjuntos que no contienen $1$ . Y para cualquier subconjunto de $A$ de $\{2,3,\dots,n\}$ tenemos que $A$ tiene una suma par si y sólo si $A\cup\{1\}$ tiene impar sum, y $A$ tiene suma impar si y sólo si $A\cup\{1\}$ tiene una suma par. Así, en general hay $2^{n-1}$ subconjuntos con suma par.

La biyección entre los conjuntos pares y los conjuntos Impares era bastante natural cuando $n\equiv 1\pmod{4}$ o $n\equiv 2\pmod{4}$ . En el caso general, existe una bonita biyección (sumar o restar $\{1\}$ ), pero es menos natural.

Answer 2

Contemos primero todos los subconjuntos de $\{1,\ldots,n\}$ con suma par. Quitando los conjuntos vacíos entonces tenemos que restar uno a este resultado.

Los subconjuntos de $\{1,\ldots,n\}$ con suma par son uno a uno con los subconjuntos de $\{2,\ldots,n\}$ . Para cualquier conjunto $J\subset\{2,\ldots,n\}$ si la suma de $J$ es par, entonces $J$ es un subconjunto de $\{1,\ldots,n\}$ con suma par, mientras que si la suma de $J$ es impar, entonces $\{1\}\cup J$ es un subconjunto con suma par.

Dado que hay $2^{n-1}$ subconjuntos de $\{2,\ldots,n\}$ es el número de subconjuntos de $\{1,\ldots,n\}$ con suma par. Si se elimina el conjunto vacío, se obtiene $2^{n-1}-1$ .

Answer 3

Lo que has hecho está bien, podemos obtener una prueba alternativa si recordamos cómo demostramos que hay $2^{n-1}$ subconjuntos de $\{1,2\dots n\}$ de cardinalidad par.

Dejemos que $E$ sea el conjunto de subconjuntos de cardinidad par y sea $O$ sea el conjunto de subconjuntos de cardinalidad impar, elija un elemento arbitrario $a\in\{1,2,3\dots n\}$ .

Entonces $f:E\rightarrow O$ definido como $X\mapsto \{a\}\Delta X$ es una biyección ¿verdad?

Bueno, si $E'$ es el conjunto de subconjuntos con suma par y $O'$ es el conjunto de subconjuntos con suma impar y $a\in\{1,2,3\dots n\}$ es impar .

$f:E'\rightarrow O'$ definido como $X\mapsto \{a\}\Delta X$ también es una biyección.

Así que en cualquier subconjunto finito $A$ de enteros positivos, exactamente la mitad de los subconjuntos tienen suma par, a menos que todos los elementos de $A$ son pares, en cuyo caso todos los subconjuntos tienen claramente suma par.

---

$\Delta$ es sólo la diferencia simétrica de conjuntos, por lo que $\{a\}\Delta X$ es $\{a\}\cup X$ si $a$ no estaba en $X$ y es $X\setminus\{a\}$ si $a$ estaba en $X$ .