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"
 
Line 11: Line 11:
  
 
==Note==
 
==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>.
+
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

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"