2020 CIME II Problems/Problem 2
Contents
Problem 2
Find the number of nonempty subsets 
of 
such that has an even number of elements, and the product of the elements of is even.
Solution
If has two elements, then there are 
subsets.
If has four elements, then there are 
subsets.
If has six elements then there are 
subsets.
If has eight elements then there are 
subsets.
If has 
elements then there is only one subset, namely .
This gives us 
subsets. However, some of these subsets do not have the property that 
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 has two elements, there are 
subsets with only odds, and if has 
elements there are 
subsets with only odds. For 
, or 
, by the pigeonhole principle, we are guaranteed to have at least one even element. The answer is thus 
.
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}.\]](http://latex.artofproblemsolving.com/c/8/c/c8c97361d6ca1d21355fc88fa56adb410b1b3b64.png)
This sum is given by the combinatorial identity and it is equal to 
or 
.
See also
| 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 | ||
The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions. 
