La probabilidad que la suma de estos números es impar es 1/2

Question

Configuración

Deje $S$ ser un conjunto de números enteros, donde al menos uno de los números enteros es un número impar. Supongamos que se elige un subconjunto aleatorio $T$ $S$ incluyendo cada elemento de a $S$ de forma independiente con una probabilidad de $1/2$, Muestran que

$$\text{Pr}\Big[\Big(\sum_{i \in T} i\Big) = \text{odd}\Big] = \frac{1}{2}$$

Solución dada

Deje $x$ ser un entero impar en $T$. A continuación, para cada subconjunto $S \subseteq T - \{x\}$, exactamente uno de $S$ $S \cup \{x\}$ tiene una extraña total, y ambos son subconjuntos de a $T$. Así, exactamente la mitad de los subconjuntos tiene un extraño total.

Problema

La solución hace muy poco sentido para mí. Si alguien tiene una solución alternativa, o podría plantear la solución más explicable manera, sería muy bueno.

Answer 1

Vamos a tratar de ampliar la oferta de demostración un poco, y ver si no tiene más sentido.

Nos encontramos con un número impar $x \in S$, ya que se dijo que uno existe, y definir $S' = S-\{x\}$. La idea central es que cada subconjunto de $S$ es un subconjunto de a $S'$, o es la unión de $\{x\}$ con un subconjunto de a $S'$, y además, que hay una correspondencia uno a uno entre el primero y el último.

Esto puede ser más claro con un ejemplo. Supongamos $S = \{1, 2, 4, 7\}$, y elegimos $x = 1$, y, a continuación,$S' = \{2, 4, 7\}$. Entonces podemos partición de los subconjuntos de a $S$ en dos partes, los que contengan $x = 1$, y los que no. Además, hay una correspondencia uno a uno entre los que tienen y los que no, a saber:

$$\{1\} \leftrightarrow \emptyset$$ $$\{1, 2\} \leftrightarrow \{2\}$$ $$\{1, 4\} \leftrightarrow \{4\}$$ $$\{1, 7\} \leftrightarrow \{7\}$$ $$\{1, 2, 4\} \leftrightarrow \{2, 4\}$$ $$\{1, 2, 7\} \leftrightarrow \{2, 7\}$$ $$\{1, 4, 7\} \leftrightarrow \{4, 7\}$$ $$\{1, 2, 4, 7\} \leftrightarrow \{2, 4, 7\}$$

Ahora, debe quedar claro que, debido a $x$ (lo que equivale $1$ en este caso) es impar, exactamente uno de los dos subconjuntos en cada emparejamiento puede tener un extraño suma. (Usted puede comprobar que por la inspección para este ejemplo, si te gusta.) Ya que todos los subconjuntos están en algún lugar de esta asignación, se deduce que exactamente la mitad de todos los subconjuntos tiene un extraño suma, y a su vez, que la probabilidad de un subconjunto (dado que cada subconjunto seleccionado con igual probabilidad) tener un extraño suma es $1/2$.

Observe que no importa si hay o no más números impares en $S$ además $x$ (como en este ejemplo); el argumento que funciona en ambos sentidos. Tenga en cuenta también que la proposición implícitamente asume que tanto el conjunto vacío y $S$ se consideran los subconjuntos de a $S$ (como es habitual), y que la suma del conjunto vacío es cero, por definición; de lo contrario, la proposición no es verdadera si los elementos de a $S$ agregar hasta un número par.

Answer 2

Lo que se quiere decir es algo como esto.

Supongamos $x$ es un extraño miembro de $S$. Para cada subconjunto $T$ que no contiene $x$, $ T \cup \{x\}$ es un subconjunto que contiene $x$. Uno de ellos tiene un extraño suma, mientras que el otro tiene incluso una suma. Cada subconjunto es de uno de los $T$'s, o uno de los $T \cup \{x\}$'s. Por lo tanto, exactamente la mitad de los posibles subconjuntos contener $x$ y la mitad no. Desde todos los subconjuntos tienen la misma probabilidad, la probabilidad de selección de un subconjunto que contiene $x$$1/2$.

Answer 3

Esta es una prueba por la vinculación - se establece un bijection entre conjuntos, incluso con sumas y establece con impar sumas, para mostrar que hay el mismo número de subconjuntos de cada tipo.

Deje $U$ ser el conjunto que contiene todos los elementos de a$S$, excepto para el. entero impar $x$.

Cada subconjunto $T$ $S$ contiene $x$ o no. Si no, a continuación, $T$ es un subconjunto de a $U$. Podemos añadir el elemento $x$ cualquier $T\subset U$ a un subconjunto $V$. Hemos partido de $T$$V$. Uno de estos conjuntos tiene incluso una suma, y el otro tiene un extraño suma.

Podemos obtener todos los posibles conjuntos de $V$? - Bueno, si tenemos un $V$ contiene $x$ que puede atacar el elemento $x$ y un $T\subset U$. Tenemos un perfecto maridaje. No podemos decir cuál de los dos conjuntos en cada uno de los tiene un extraño suma, pero sabemos que precisamente uno de ellos.

Por lo tanto, sé que la mitad de los conjuntos tienen impar sumas y la mitad tiene incluso sumas.

Answer 4

Podemos hacer caso omiso de todos los elementos de a $S$, como que no afecten a la paridad de la suma. Así que vamos a $N$ el número de elementos de a $S$, de los cuales todos son impares. Dicen que esos elementos se $x_1, x_2, \ldots, x_N$.

Deje $S_k = \{x_1, \ldots, x_k\}$ (conjunto parcial de la primera $k$ elementos de $S$), y deje $t_k$ la suma de los elementos de $S_k$ que es recogido.

Elemento $x_1$ es recogido con una probabilidad de $1/2$. Por lo que el $t_1$ es impar con una probabilidad de $1/2$.

Elemento $x_2$ es captado también con probabilidad de $1/2$. Por lo que la paridad de $t_2$ difiere de la de $t_1$ con una probabilidad de $1/2$. Esto implica que $t_2$ es de nuevo el extraño con una probabilidad de $1/2$.

Se puede proceder de forma similar para todos los $x_3, \ldots, x_k$. (Por supuesto, esto podría ser más formal con la inducción).