Difference between revisions of "2017 AIME I Problems/Problem 12"

(Created page with "==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=...")
 
m
Line 1: Line 1:
 +
==Problem 12==
 +
Call a set <math>S</math> product-free if there do not exist <math>a, b, c \in S</math> (not necessarily distinct) such that <math>a b = c</math>. For example, the empty set and the set <math>\{16, 20\}</math> are product-free, whereas the sets <math>\{4, 16\}</math> and <math>\{2, 8, 16\}</math> are not product-free. Find the number of product-free subsets of the set <math>\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}</math>.
 +
 
==Solution==
 
==Solution==
  
Line 8: Line 11:
  
 
So our answer is <math>60+64+128=\boxed{252}</math>.
 
So our answer is <math>60+64+128=\boxed{252}</math>.
 +
 +
==See Also==
 +
{{AIME box|year=2017|n=I|num-b=11|num-a=13}}
 +
{{MAA Notice}}

Revision as of 20:27, 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 (ProblemsAnswer KeyResources)
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

Invalid username
Login to AoPS