Intuitive proof for a Combinatorial Problem

Question

Given a set $S$ such that $|S|=N$ and $S$ contains exactly $K$ $0$s $(0<K <N)$ and $N-K$ $1$s, then exactly half of the subsets of $S$ contain an $odd$ number of 1s, $indepedent$ of the value of $K$.

I have the following proof for this:

Number of subsets formed with $N-K$ zeroes is $2^{N-K}$. For each of this subset the number of ways in which I can select an odd number ones is: $$\sum_{n=1}^{N/2}\binom{K}{2n-1}= 2^{K-1}$$ Then the total subsets with $odd$ number of one's is $2^{N-1}$.

However I was looking for an intuitive proof for this.

Answer 1

You need to assume that $K<N$, not that $K>0$: you want to be sure that there is at least one $1$. Call a subset of $S$ odd if it contains an odd number of ones and even otherwise.

First suppose that $N-K$ is odd. If $A$ is any subset of $S$, those $N-K$ ones are split between $A$ and $S\setminus A$, so exactly one of these complementary sets is odd. Since exactly one of each pair of complementary subsets of $S$ is odd, exactly half of the subsets of $S$ are odd.

Now suppose that $N-K$ is even. $S$ contains at least one $1$, so we may remove it to leave a set $S'$ with an odd number of ones. By the previous paragraph we know that half of the subsets of $S'$ are odd. Now look at the subsets of $S$ that include the $1$ that we removed to get $S'$. These are precisely the subsets of $S$ that we get by adding that missing $1$ to each of the subsets of $S'$. Doing so changes odd subsets of $S'$ to even subsets of $S$, and even subsets of $S'$ to odd subsets of $S$; half of the subsets of $S'$ are odd, so half of the subsets of $S$ that contain that missing $1$ are even, and hence the other half are odd. Thus, half of the subsets of $S$ that don’t contain that $1$ are odd, and half of those that do contain it are odd, and therefore half of the subsets of $S$ are odd.

Answer 2

I believe the condition you need is $K < N$. Otherwise, consider $S$ a set of all $0$s. Anyway, can you find a simple 1 to 1 pairing between sets containing an odd number of $1$s and an even number of $1$s?

Hint: Set one of the $1$s aside and try to find said pairing.

Answer 3

(As others have remarked we have to assume $K<N$.)

We are given a finite set $S$ and a function $f:\>S\to\{0,1\}$ with $f(a)=1$ for at least one $a\in S$. Then each subset $A\subset S$ has a parity $$p(A):=\sum_{x\in A}f(x)\quad{\rm mod}\ 2\ .$$

For any subset $A'\subset S':=S\setminus\{a\}$ the two sets $A_0:=A'$ and $A_1:=A'\cup\{a\}$ have different parities. Since ${\cal P}(S)\cong {\cal P}(S')\times\bigl\{\emptyset,\{a\}\bigr\}$ in a natural way it follows that $p(A)=1$ for exactly half of the sets $A\in{\cal P}(S)$.