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

m (Solution 3)
m (Solution 3)
Line 25: Line 25:
  
 
==Solution 3==
 
==Solution 3==
Let <math>X</math> be a product-free subset, and note that 1 is not in <math>x</math>. We consider four cases: 1.) both 2 and 3 are not in <math>X</math>. Then there are <math>2^7=128</math> possible subsets for this case. 2.) 2 is in <math>X</math>, but 3 is not. Then 4 in not in <math>X</math>, so there are <math>2^6=64</math> subsets; however, there is a <math>\frac{1}{4}</math> chance that 5 and 10 are both in <math>X</math>, so there are <math>64\cdot \frac{3}{4}=48</math> subsets for this case. 3.) 2 is not in <math>X</math>, but 3 is. Then, 9 is not in <math>X</math>, so there are <math>2^6=64</math> subsets for this case. 4.) 2 and 3 are both in <math>X</math>. Then, 4, 6, and 9 are not in <math>X</math>, so there are <math>2^4=16</math> total subsets; however, there is a <math>\frac{1}{4}</math> chance that 5 and 10 are both in <math>X</math>, so there are <math>16\cdot \frac{3}{4}=12</math> subsets for this case.
+
Let <math>X</math> be a product-free subset, and note that 1 is not in <math>x</math>. We consider four cases:  
Hence our answer is <math>128+48+64+12=\boxed{252}</math>. -Stormersyle sucks
+
 
 +
1.) both 2 and 3 are not in <math>X</math>. Then there are <math>2^7=128</math> possible subsets for this case.  
 +
 
 +
2.) 2 is in <math>X</math>, but 3 is not. Then 4 in not in <math>X</math>, so there are <math>2^6=64</math> subsets; however, there is a <math>\frac{1}{4}</math> chance that 5 and 10 are both in <math>X</math>, so there are <math>64\cdot \frac{3}{4}=48</math> subsets for this case.  
 +
 
 +
3.) 2 is not in <math>X</math>, but 3 is. Then, 9 is not in <math>X</math>, so there are <math>2^6=64</math> subsets for this case.  
 +
 
 +
4.) 2 and 3 are both in <math>X</math>. Then, 4, 6, and 9 are not in <math>X</math>, so there are <math>2^4=16</math> total subsets; however, there is a <math>\frac{1}{4}</math> chance that 5 and 10 are both in <math>X</math>, so there are <math>16\cdot \frac{3}{4}=12</math> subsets for this case.
 +
 
 +
Hence our answer is <math>128+48+64+12=\boxed{252}</math>. -Stormersyle
  
 
==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 12:00, 1 December 2019

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)

We will consider the $2^9 = 512$ subsets that do not contain 1. A subset is product-free if and only if it does not contain one of the groups $\{2, 4\}, \{3, 9\}, \{2, 3, 6\},$ or $\{2, 5, 10\}$. There are $2^7$ subsets that contain 2 and 4 since each of the seven elements other than 2 and 4 can either be in the subset or not. Similarly, there are $2^7$ subsets that contain 3 and 9, $2^6$ subsets that contain 2, 3, and 6, and $2^6$ subsets that contain 2, 5, and 10. The number of sets that contain one of the groups is: \[2^7 + 2^7 + 2^6 + 2^6 = 384\] For sets that contain two of the groups, we have: \[2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4 = 160\] For sets that contain three of the groups, we have: \[2^4 + 2^3 + 2^3 + 2^3 = 40\] For sets that contain all of the groups, we have: \[2^2 = 4\] By the principle of inclusion and exclusion, the number of product-free subsets is \[512 - (384 - 160 + 40 - 4) = \boxed{252}\].

Solution 3

Let $X$ be a product-free subset, and note that 1 is not in $x$. We consider four cases:

1.) both 2 and 3 are not in $X$. Then there are $2^7=128$ possible subsets for this case.

2.) 2 is in $X$, but 3 is not. Then 4 in not in $X$, so there are $2^6=64$ subsets; however, there is a $\frac{1}{4}$ chance that 5 and 10 are both in $X$, so there are $64\cdot \frac{3}{4}=48$ subsets for this case.

3.) 2 is not in $X$, but 3 is. Then, 9 is not in $X$, so there are $2^6=64$ subsets for this case.

4.) 2 and 3 are both in $X$. Then, 4, 6, and 9 are not in $X$, so there are $2^4=16$ total subsets; however, there is a $\frac{1}{4}$ chance that 5 and 10 are both in $X$, so there are $16\cdot \frac{3}{4}=12$ subsets for this case.

Hence our answer is $128+48+64+12=\boxed{252}$. -Stormersyle

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