2020 CIME II Problems/Problem 2
Contents
[hide]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 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.