1
$\begingroup$

Let $n_{odd}$ represents the number of odd numbers in the set $S$ and $n_{even}$ denote the number of even numbers. The total number of possible subsets formed with odd count of odd numbers $=2^{n_{odd}-1} \cdot 2^{n_{even}}$. How do we prove this ?

$\endgroup$
  • $\begingroup$ Let $O$ be the set of odd numbers in $S$. Half the subsets of $O$ have an odd number of odds. $\endgroup$ – André Nicolas Mar 30 '16 at 21:52
1
$\begingroup$

Let $E$ be the set of even numbers in $S$, and $O$ the set of odd numbers in $S$. We assume (this is not stated explicitly in the post) that $O$ is non-empty.

Any subset of $S$ with an odd number of odds can be uniquely expressed as $A\cup B$, where $A$ is a subset of $O$ with an odd number of odds, and $B$ is any subset of $E$.

For any choice of $A$, there are $2^{n_{\text{even}}}$ ways to choose $B$. It remains to show that there are $2^{n_{\text{odd}}-1}$ ways to choose $A$.

So we want to count the number of odd subsets of $O$. Arrange the $n_{\text{odd}}$ elements of $O$ in order. Call them $x_1$ to $x_k$. Any subset of $O$ with an odd number of elements can be uniquely constructed as follows. Choose any subset of $\{x_1,\dots, x_{k-1}\}$. If this subset has an odd number of elements, keep the subset. If if has an even number of elements, append $x_k$ to the set, to make the count of odds odd.

So there are just as many subsets of $\{x_1,\dots,x_k\}$ with an odd number of elements as there are subsets of $\{x_1,\dots, x_{k-1}\}$, that is, $2^{k-1}$. In our case $k=n_{\text{odd}}$, so we are finished.

Another way: We sketch a much simpler approach based on the same idea. Suppose $a$ is a fixed odd number in $S$. Call a subset of $S$ good if it has an odd number of odd numbers. We count the good subsets of $S$.

There are just as many good subsets of $S$ as there are subsets of $S\setminus \{a\}$. For a subset $K$ of $S\setminus\{a\}$ is either good or not good. But if $K$ is not good, then $K\cup\{a\}$ is good. And every good subset of $S$ can be produced in this way.

Thus the number of good subsets of $S$ is $2^{m-1}$, where $m$ is the number of elements of $S$. Finally, note that $m=n_{\text{odd}}+n_{\text{even}}$, and therefore $2^{n_{\text{odd}}-1}\cdot 2^{n_{\text{even}}}=2^{m-1}$.

$\endgroup$
  • $\begingroup$ Nicolas can you please elaborate this line more in your second approach "There are just as many good subsets of SS as there are subsets of S∖{a}S∖{a}. For a subset KK of S∖{a}S∖{a}, is either good, or appending aa to it makes it good." $\endgroup$ – satyajeet jha Mar 31 '16 at 0:34
  • 1
    $\begingroup$ Let $S_a=S\setminus\{a\}$ (everybody but $a$), and take any subset $K$ of $S_a$. Maybe $K$ has an odd number of odds (is good). Or maybe it has an even number of odds, in which case $K\cup \{a\}$ is good. So given any subset of $S_a$, we can produce a good subset of $S$ using this procedure. Conversely, any good subset of $S$ can be produced in this way, for a good subset either does not contain $a$, so must be a good subset of $S_a$, or does contain $a$, so must have been produced by adding $a$ to a bad subset of $S_a$. $\endgroup$ – André Nicolas Mar 31 '16 at 0:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.