2020 CIME II Problems/Problem 2

Problem 2

Find the number of nonempty subsets $S$ of $\{1,2,3,4,5,6,7,8,9,10\}$ such that $S$ has an even number of elements, and the product of the elements of $S$ is even.

Solution

If $S$ has two elements, then there are $\binom{10}{2}=45$ subsets. If $S$ has four elements, then there are $\binom{10}{4}=210$ subsets. If $S$ has six elements then there are $\binom{10}{6}=210$ subsets. If $S$ has eight elements then there are $\binom{10}{8}=45$ subsets. If $S$ has $10$ elements then there is only one subset, namely $\{1,2,3,4,5,6,7,8,9,10\}$. This gives us $45+210+210+45+1=511$ subsets. However, some of these subsets do not have the property that $\prod S$ is even, that is, it is not true that the subset has at least one even element, so all of the elements must be odd. If $S$ has two elements, there are $\binom{5}{2}=10$ subsets with only odds, and if $S$ has $4$ elements there are $\binom{5}{4}=5$ subsets with only odds. For $|S|=6, |S|=8$, or $|S|=10$, by the pigeonhole principle, we are guaranteed to have at least one even element. The answer is thus $511-10-5=\boxed{496}$.

Note

We did not actually have to compute each of the values to compute the sum \[\binom{10}{2}+\binom{10}{4}+\binom{10}{6}+\binom{10}{8}+\binom{10}{10}.\] This sum is given by the combinatorial identity and it is equal to $\frac{2^{10}}{2}-1$ or $511$.

See also

2020 CIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All CIME Problems and Solutions

The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions. AMC logo.png