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 "2017 AIME II Problems/Problem 1"

(→‎Solution)
Line 7: Line 7:
 
==Solution 2==  
 
==Solution 2==  
 
Upon inspection, a viable set must contain at least one element from both of the sets <math>\{1, 2, 3, 4, 5\}</math> and <math>\{4, 5, 6, 7, 8\}</math>. Since 4 and 5 are included in both of these sets, then they basically don't matter, i.e. if set A is a subset of both of those two then adding a 4 or a 5 won't change that fact. Thus, we can count the number of ways to choose at least one number from 1 to 3 and at least one number from 6 to 8, and then multiply that by the number of ways to add in 4 and 5. The number of subsets of a 3 element set is <math>2^3=8</math>, but we want to exclude the empty set, giving us 7 ways to choose from  <math>\{1, 2, 3\}</math> or <math>\{4, 5, 6\}</math>. We can take each of these <math>7 \times 7=49</math> sets and add in a 4 and/or a 5, which can be done in 4 different ways (by adding both, none, one, or the other one). Thus, the answer is <math>49 \times 4=\boxed{196}</math>.
 
Upon inspection, a viable set must contain at least one element from both of the sets <math>\{1, 2, 3, 4, 5\}</math> and <math>\{4, 5, 6, 7, 8\}</math>. Since 4 and 5 are included in both of these sets, then they basically don't matter, i.e. if set A is a subset of both of those two then adding a 4 or a 5 won't change that fact. Thus, we can count the number of ways to choose at least one number from 1 to 3 and at least one number from 6 to 8, and then multiply that by the number of ways to add in 4 and 5. The number of subsets of a 3 element set is <math>2^3=8</math>, but we want to exclude the empty set, giving us 7 ways to choose from  <math>\{1, 2, 3\}</math> or <math>\{4, 5, 6\}</math>. We can take each of these <math>7 \times 7=49</math> sets and add in a 4 and/or a 5, which can be done in 4 different ways (by adding both, none, one, or the other one). Thus, the answer is <math>49 \times 4=\boxed{196}</math>.
 +
 +
==Solution 3==
 +
 +
Name a valid set <math>S</math> If its intersection with <math>\{4,5\}</math> is <math>\varnothing</math>. Its intersection with sets <math>\{1,2,3\}</math> and <math>\{6,7,8\}</math> must not be <math>\varnothing</math>. There are <math>7\cdot7=49</math> ways to choose these sets. The union of valid sets <math>S</math> and <math>\varnothing</math>, <math>\{4\}</math>, <math>\{5\}</math>, and <math>\{4,5\}</math> produce all the valid sets. There are <math>49\cdot4=\boxed{196}</math> sets in question. <math>\blacksquare</math>
 +
 +
Solution by [[User:a1b2]]
  
 
=See Also=
 
=See Also=
 
{{AIME box|year=2017|n=II|before=First Problem|num-a=2}}
 
{{AIME box|year=2017|n=II|before=First Problem|num-a=2}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 14:47, 29 March 2017

Problem

Find the number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}$.

Solution 1

The number of subsets of a set with $n$ elements is $2^n$. The total number of subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ is equal to $2^8$. The number of sets that are subsets of at least one of $\{1, 2, 3, 4, 5\}$ or $\{4, 5, 6, 7, 8\}$ can be found using complimentary counting. There are $2^5$ subsets of $\{1, 2, 3, 4, 5\}$ and $2^5$ subsets of $\{4, 5, 6, 7, 8\}$. It is easy to make the mistake of assuming there are $2^5+2^5$ sets that are subsets of at least one of $\{1, 2, 3, 4, 5\}$ or $\{4, 5, 6, 7, 8\}$, but the $2^2$ subsets of $\{4, 5\}$ are overcounted. There are $2^5+2^5-2^2$ sets that are subsets of at least one of $\{1, 2, 3, 4, 5\}$ or $\{4, 5, 6, 7, 8\}$, so there are $2^8-(2^5+2^5-2^2)$ subsets of $\{1, 2, 3, 4, 5, 6, 7, 8\}$ that are subsets of neither $\{1, 2, 3, 4, 5\}$ nor $\{4, 5, 6, 7, 8\}$. $2^8-(2^5+2^5-2^2)=\boxed{196}$.

Solution 2

Upon inspection, a viable set must contain at least one element from both of the sets $\{1, 2, 3, 4, 5\}$ and $\{4, 5, 6, 7, 8\}$. Since 4 and 5 are included in both of these sets, then they basically don't matter, i.e. if set A is a subset of both of those two then adding a 4 or a 5 won't change that fact. Thus, we can count the number of ways to choose at least one number from 1 to 3 and at least one number from 6 to 8, and then multiply that by the number of ways to add in 4 and 5. The number of subsets of a 3 element set is $2^3=8$, but we want to exclude the empty set, giving us 7 ways to choose from $\{1, 2, 3\}$ or $\{4, 5, 6\}$. We can take each of these $7 \times 7=49$ sets and add in a 4 and/or a 5, which can be done in 4 different ways (by adding both, none, one, or the other one). Thus, the answer is $49 \times 4=\boxed{196}$.

Solution 3

Name a valid set $S$ If its intersection with $\{4,5\}$ is $\varnothing$. Its intersection with sets $\{1,2,3\}$ and $\{6,7,8\}$ must not be $\varnothing$. There are $7\cdot7=49$ ways to choose these sets. The union of valid sets $S$ and $\varnothing$, $\{4\}$, $\{5\}$, and $\{4,5\}$ produce all the valid sets. There are $49\cdot4=\boxed{196}$ sets in question. $\blacksquare$

Solution by User:a1b2

See Also

2017 AIME II (Problems • Answer Key • Resources)
Preceded by
First Problem 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_AIME_II_Problems/Problem_1&oldid=85064"