Difference between revisions of "2020 CIME II Problems/Problem 2"
| (One intermediate revision 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== | ||
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 ![\[\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. 
