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$ .

2020 CIME II (Problems • Answer Key • Resources)
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

Page

Toolbox

Search

2020 CIME II Problems/Problem 2

Contents

Problem 2

Solution

Note

See also