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"

m
m (bottom box, formatting)
Line 4: Line 4:
 
==Solution==
 
==Solution==
  
−
We shall solve this problem by doing casework on the lowest element of the subset. Note that the number <math>1</math> cannot be in the subset because <math>1*1=1</math>. Let S be a product-free set. If the lowest element of S is <math>2</math>, we consider the set {3, 6, 9}. We see that <math>5</math> 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 <math>3</math> of these subsets can be a subset of S ({5}, {10}, and the empty set). Note that <math>4</math> cannot be an element of S, because <math>2</math> 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 <math>2</math>, there are <math>5*3*4=60</math> possible such sets.
+
We shall solve this problem by doing casework on the lowest element of the subset. Note that the number <math>1</math> cannot be in the subset because <math>1*1=1</math>. Let <math>S</math> be a product-free set. If the lowest element of <math>S</math> is <math>2</math>, we consider the set <math>\{3, 6, 9\}</math>. We see that 5 of these subsets can be a subset of <math>S</math> (<math>\{3\}</math>, <math>\{6\}</math>, <math>\{9\}</math>, <math>\{6, 9\}</math>, and the empty set). Now consider the set <math>\{5, 10\}</math>. We see that 3 of these subsets can be a subset of <math>S</math> (<math>\{5\}</math>, <math>\{10\}</math>, and the empty set). Note that <math>4</math> cannot be an element of <math>S</math>, because <math>2</math> is. Now consider the set <math>\{7, 8\}</math>. All four of these subsets can be a subset of <math>S</math>. So if the smallest element of <math>S</math> is <math>2</math>, there are <math>5*3*4=60</math> possible such sets.
  
−
If the smallest element of S is <math>3</math>, the only restriction we have is that <math>9</math> is not in S. This leaves us <math>2^6=64</math> such sets.
+
If the smallest element of <math>S</math> is <math>3</math>, the only restriction we have is that <math>9</math> is not in <math>S</math>. This leaves us <math>2^6=64</math> such sets.
  
−
If the smallest element of S is not <math>2</math> or <math>3</math>, then S can be any subset of {4, 5, 6, 7, 8, 9, 10}, including the empty set. This gives us <math>2^7=128</math> such subsets.
+
If the smallest element of <math>S</math> is not <math>2</math> or <math>3</math>, then <math>S</math> can be any subset of <math>\{4, 5, 6, 7, 8, 9, 10\}</math>, including the empty set. This gives us <math>2^7=128</math> such subsets.
  
 
So our answer is <math>60+64+128=\boxed{252}</math>.
 
So our answer is <math>60+64+128=\boxed{252}</math>.

Revision as of 19:30, 8 March 2017

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

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

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=84527"