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 I Problems/Problem 12"

(→‎Solution 2(PIE) (Should be explained in more detail))
m (→‎Solution 2(PIE) (Should be explained in more detail))
Line 15: Line 15:
 
We cannot have the following pairs or triplets: <math>\{2, 4\}, \{3, 9\}, \{2, 3, 6\}, \{2, 5, 10\}</math>.
 
We cannot have the following pairs or triplets: <math>\{2, 4\}, \{3, 9\}, \{2, 3, 6\}, \{2, 5, 10\}</math>.
 
Since there are <math>2^9</math> = <math>512</math> subsets(<math>1</math> isn't needed) we have the following:
 
Since there are <math>2^9</math> = <math>512</math> subsets(<math>1</math> isn't needed) we have the following:
−
The total number of sets with at least one of the groups (with repeats)
+
<math>...</math> The total number of sets with at least one of the groups (with repeats)
 
=<math>2^7 + 2^7 + 2^6 + 2^6</math>
 
=<math>2^7 + 2^7 + 2^6 + 2^6</math>
 
= <math>384</math>
 
= <math>384</math>
−
The total number of sets with at least two of the groups (with repeats)
+
<math>...</math> The total number of sets with at least two of the groups (with repeats)
 
= 1st & 2nd pair <math>+</math> 1st & 3rd pair <math>+</math> 1st & 4th pair <math>+</math> 2nd & 3rd pair <math>+</math> 2nd & 4th pair <math>+</math> 3rd & 4th pair  
 
= 1st & 2nd pair <math>+</math> 1st & 3rd pair <math>+</math> 1st & 4th pair <math>+</math> 2nd & 3rd pair <math>+</math> 2nd & 4th pair <math>+</math> 3rd & 4th pair  
 
= <math>2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4</math>
 
= <math>2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4</math>
 
= <math>160</math>
 
= <math>160</math>
−
The total number of sets with at least three of the groups (with repeats)
+
<math>...</math> The total number of sets with at least three of the groups (with repeats)
 
= 1st, 2nd, & 3rd groups <math>+</math> 1st, 2nd & 4th groups <math>+</math> 1st, 3rd, & 4th groups <math>+</math> 2nd, 3rd, & 4th groups
 
= 1st, 2nd, & 3rd groups <math>+</math> 1st, 2nd & 4th groups <math>+</math> 1st, 3rd, & 4th groups <math>+</math> 2nd, 3rd, & 4th groups
 
= <math>2^4 + 2^3 + 2^3 + 2^3</math>
 
= <math>2^4 + 2^3 + 2^3 + 2^3</math>
 
= <math>40</math>
 
= <math>40</math>
−
The total number of sets with all of the groups.
+
<math>...</math> The total number of sets with all of the groups.
 
= <math>2^2</math>
 
= <math>2^2</math>
 
= <math>4</math>
 
= <math>4</math>
 
<math>(512-(384-160+40-4)) \implies \boxed{252}</math>.
 
<math>(512-(384-160+40-4)) \implies \boxed{252}</math>.
 +
(Note: If someone can add breaks and maybe help explain why there are powers of 2 that would be good)
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2017|n=I|num-b=11|num-a=13}}
 
{{AIME box|year=2017|n=I|num-b=11|num-a=13}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 22:55, 20 March 2018

Problem 12

Call a set $S$ product-free if there do not exist $a, b, c \in S$ (not necessarily distinct) such that $a b = c$. For example, the empty set and the set $\{16, 20\}$ are product-free, whereas the sets $\{4, 16\}$ and $\{2, 8, 16\}$ are not product-free. Find the number of product-free subsets of the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$.

Solution 1(Casework)

We shall solve this problem by doing casework on the lowest element of the subset. Note that the number $1$ cannot be in the subset because $1*1=1$. Let $S$ be a product-free set. If the lowest element of $S$ is $2$, we consider the set $\{3, 6, 9\}$. We see that 5 of these subsets can be a subset of $S$ ($\{3\}$, $\{6\}$, $\{9\}$, $\{6, 9\}$, and the empty set). Now consider the set $\{5, 10\}$. We see that 3 of these subsets can be a subset of $S$ ($\{5\}$, $\{10\}$, and the empty set). Note that $4$ cannot be an element of $S$, because $2$ is. Now consider the set $\{7, 8\}$. All four of these subsets can be a subset of $S$. So if the smallest element of $S$ is $2$, there are $5*3*4=60$ possible such sets.

If the smallest element of $S$ is $3$, the only restriction we have is that $9$ is not in $S$. This leaves us $2^6=64$ such sets.

If the smallest element of $S$ is not $2$ or $3$, then $S$ can be any subset of $\{4, 5, 6, 7, 8, 9, 10\}$, including the empty set. This gives us $2^7=128$ such subsets.

So our answer is $60+64+128=\boxed{252}$.

Solution 2(PIE) (Should be explained in more detail)

We cannot have the following pairs or triplets: $\{2, 4\}, \{3, 9\}, \{2, 3, 6\}, \{2, 5, 10\}$. Since there are $2^9$ = $512$ subsets($1$ isn't needed) we have the following: $...$ The total number of sets with at least one of the groups (with repeats) =$2^7 + 2^7 + 2^6 + 2^6$ = $384$ $...$ The total number of sets with at least two of the groups (with repeats) = 1st & 2nd pair $+$ 1st & 3rd pair $+$ 1st & 4th pair $+$ 2nd & 3rd pair $+$ 2nd & 4th pair $+$ 3rd & 4th pair = $2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4$ = $160$ $...$ The total number of sets with at least three of the groups (with repeats) = 1st, 2nd, & 3rd groups $+$ 1st, 2nd & 4th groups $+$ 1st, 3rd, & 4th groups $+$ 2nd, 3rd, & 4th groups = $2^4 + 2^3 + 2^3 + 2^3$ = $40$ $...$ The total number of sets with all of the groups. = $2^2$ = $4$ $(512-(384-160+40-4)) \implies \boxed{252}$. (Note: If someone can add breaks and maybe help explain why there are powers of 2 that would be good)

See Also

2017 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 11 		Followed by
Problem 13
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_I_Problems/Problem_12&oldid=93355"