Show the probability that the sum of these numbers is odd is 1/2

Question

Setting

Let $S$ be a set of integers where at least one of the integers is odd. Suppose we pick a random subset $T$ of $S$ by including each element of $S$ independently with probability $1/2$, Show that

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

Solution given

Let $x$ be an odd integer in $T$. Then for every subset $S \subseteq T - \{x\}$, exactly one of $S$ and $S \cup \{x\}$ has an odd total, and both are subsets of $T$. Thus exactly half of the subsets have an odd total.

Problem

The solution makes very little sense to me. If someone has an alternate solution, or could pose the solution in a more explicable manner, it'd be really nice.

Answer 1

Let's try to expand the offered demonstration a bit, and see if it doesn't make more sense.

We find an odd number $x \in S$, since we are told one exists, and define $S' = S-\{x\}$. The central idea is that every subset of $S$ is then either a subset of $S'$, or it's the union of $\{x\}$ with a subset of $S'$, and furthermore, that there is a one-to-one correspondence between the former and the latter.

This may be made clearer with an example. Suppose $S = \{1, 2, 4, 7\}$, and we choose $x = 1$, and then $S' = \{2, 4, 7\}$. Then we can partition the subsets of $S$ into two parts, those that contain $x = 1$, and those that do not. Furthermore, there is a one-to-one correspondence between those that do and those that do not: namely

$$\{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\}$$

Now, it should be clear that because $x$ (which equals $1$ in this case) is odd, exactly one of the two subsets in each pairing can have an odd sum. (You can verify that by inspection for this example, if you like.) Since all the subsets are somewhere in this mapping, it follows that exactly half of all subsets have an odd sum, and in turn, that the probability of a subset (given that each subset is selected with equal probability) having an odd sum is $1/2$.

Notice that it does not matter whether or not there are more odd numbers in $S$ besides $x$ (as there is in this example); the argument works either way. Note also that the proposition implicitly assumes that both the empty set and $S$ are considered to be subsets of $S$ (as is typical), and that the sum of the empty set is zero, by definition; otherwise, the proposition is not true if the elements of $S$ add up to an even number.

Answer 2

What was meant is something like this.

Suppose $x$ is an odd member of $S$. For each subset $T$ that doesn't contain $x$, $ T \cup \{x\}$ is a subset that does contain $x$. One of them has an odd sum while the other has an even sum. Every subset is either one of the $T$'s or one of the $T \cup \{x\}$'s. Therefore exactly half of the possible subsets contain $x$ and half do not. Since all subsets have equal probability, the probability of selecting a subset that contains $x$ is $1/2$.

Answer 3

This is a proof by pairing - it establishes a bijection between sets with even sums and sets with odd sums, to show that there are the same number of subsets of each kind.

Let $U$ be the set which contains all the elements of $S$ except for the. odd integer $x$.

Every subset $T$ of $S$ either contains $x$ or it doesn't. If it doesn't then $T$ is a subset of $U$. We can add the element $x$ to any set $T\subset U$ to get a subset $V$. We match $T$ with $V$. One of these sets has an even sum, and the other has an odd sum.

Do we get all the possible sets $V$? - Well if we have a $V$ containing $x$ we can strike out the element $x$ and get a set $T\subset U$. We have a perfect matching. We can't tell which of the two sets in each matching has an odd sum, but we know precisely one of them will.

We therefore know that half of the sets have odd sums and half have even sums.

Answer 4

We can disregard all even elements from $S$, as they don't affect the parity of the sum. So let $N$ be the number of elements from $S$, all of which are odd. Say those elements are $x_1, x_2, \ldots, x_N$.

Let $S_k = \{x_1, \ldots, x_k\}$ (partial set of the first $k$ elements of $S$), and let $t_k$ be the sum of the elements from $S_k$ that get picked.

Element $x_1$ is picked with probability $1/2$. So the $t_1$ is odd with probability $1/2$.

Element $x_2$ is also picked with probability $1/2$. So the parity of $t_2$ differs from that of $t_1$ with probability $1/2$. This implies that $t_2$ is again odd with probability $1/2$.

You can proceed similarly for all $x_3, \ldots, x_k$. (Of course this could be made more formal with induction).