How many nonempty subsets of $\{1,2,\dots 10\}$ have the product of their elements even?

How many nonempty subsets of $\{1,2,\dots 10\}$ have the product of their elements even?

There are $2^{10}$ subsets of $\{1,2,\dots 10\}$. Now I'm trying to approach this by counting the complement and then subtracting it from the total cases.

The product of the elements is odd if each of the elements is odd. There are $5$ odd elements in $\{1,2,\dots 10\}$. So the number of ways to choose subsets of $\{1,2,\dots 10\}$ where all the elements are odd is $\binom{10}{5}$. So is the answer $$2^{10}- \binom{10}{5}?$$

Solution 1:

The product of all the elements in a set of integers is even unless all of the elements in that set are odd. Thus, we need to subtract the number of subsets containing only odd elements from the number of subsets.

A set with $n$ elements has $2^n$ subsets, one of which is the empty set. Thus, the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ has $2^{10}$ subsets, one of which is the empty set. A subset containing only odd elements must be a subset of the subset $\{1, 3, 5, 7, 9\}$. There are $2^5$ subsets of the set $\{1, 3, 5, 7, 9\}$, one of which is the empty set. Thus, the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ in which the product of all of its elements is even is $$2^{10} - 2^5$$ Observe that each of these $2^{10} - 2^{5}$ subsets are nonempty since the empty set was among the sets we removed when we subtracted.

As J. G. explained in the comments, $\binom{10}{5}$ counts the number of subsets with five elements that can be selected from a set with ten elements. Since exactly five of the ten elements in the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ are odd, only one of these contains only odd elements.