Let S=1,2,3,,100.

Question

Let $S=\{1,2,3,\ldots,100\}$. The number of non-empty subsets $A$ of $S$ such that the product of elements in $A$ is even is:

Accepted Answer

The product of a subset's elements is even iff it contains at least one even number. Equivalently, exclude subsets that are entirely odd.

Total non-empty subsets: $2^{100}-1$. Non-empty all-odd subsets: $2^{50}-1$ (there are 50 odd numbers in $S$).

$$(2^{100}-1) - (2^{50}-1) = 2^{100}-2^{50} = 2^{50}(2^{50}-1)$$

Solutions · 1