Difference between revisions of "2020 CIME II Problems/Problem 2"
(2 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
==Problem 2== | ==Problem 2== | ||
− | Find the number of nonempty subsets <math>S</math> of <math>\{1,2,3, | + | Find the number of nonempty subsets <math>S</math> of <math>\{1,2,3,4,5,6,7,8,9,10\}</math> such that <math>S</math> has an even number of elements, and the product of the elements of <math>S</math> is even. |
==Solution== | ==Solution== | ||
+ | If <math>S</math> has two elements, then there are <math>\binom{10}{2}=45</math> subsets. | ||
+ | If <math>S</math> has four elements, then there are <math>\binom{10}{4}=210</math> subsets. | ||
+ | If <math>S</math> has six elements then there are <math>\binom{10}{6}=210</math> subsets. | ||
+ | If <math>S</math> has eight elements then there are <math>\binom{10}{8}=45</math> subsets. | ||
+ | If <math>S</math> has <math>10</math> elements then there is only one subset, namely <math>\{1,2,3,4,5,6,7,8,9,10\}</math>. | ||
+ | This gives us <math>45+210+210+45+1=511</math> subsets. However, some of these subsets do not have the property that <math>\prod S</math> 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 <math>S</math> has two elements, there are <math>\binom{5}{2}=10</math> subsets with only odds, and if <math>S</math> has <math>4</math> elements there are <math>\binom{5}{4}=5</math> subsets with only odds. For <math>|S|=6, |S|=8</math>, or <math>|S|=10</math>, by the [[Pigeonhole principle|pigeonhole principle]], we are guaranteed to have at least one even element. The answer is thus <math>511-10-5=\boxed{496}</math>. | ||
+ | |||
+ | ==Note== | ||
+ | We did not actually have to compute each of the values to compute the sum <cmath>\binom{10}{2}+\binom{10}{4}+\binom{10}{6}+\binom{10}{8}+\binom{10}{10}.</cmath> This sum is given by the [[Combinatorial identity|combinatorial identity]] and it is equal to <math>\frac{2^{10}}{2}-1</math> or <math>511</math>. | ||
==See also== | ==See also== | ||
Line 8: | Line 17: | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
− | {{ | + | {{MAC Notice}} |
Latest revision as of 22:51, 5 September 2020
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 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.