Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 CIME II Problems/Problem 2"
 
(4 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,\ldots,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.
+
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==
−
{{CIME box|n=II|year=2020|num-b=1|num=a=3}}
+
{{CIME box|year=2020|n=II|num-b=1|num-a=3}}
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
−
{{MAA Notice}}
+
{{MAC Notice}}

Latest revision as of 23:51, 5 September 2020

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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_CIME_II_Problems/Problem_2&oldid=133256"