Difference between revisions of "2017 AIME I Problems/Problem 12"
m (→Solution 2(PIE) (Should be explained in more detail)) |
|||
(7 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
==Problem 12== | ==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, | + | 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,..., 7, 8, 9, 10\}</math>. |
− | ==Solution 1(Casework)== | + | ==Solution 1 (Casework)== |
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. | 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. | ||
Line 12: | Line 12: | ||
So our answer is <math>60+64+128=\boxed{252}</math>. | So our answer is <math>60+64+128=\boxed{252}</math>. | ||
− | ==Solution 2(PIE | + | ==Solution 2 (PIE)== |
− | We | + | We will consider the <math>2^9 = 512</math> subsets that do not contain 1. A subset is product-free if and only if it does not contain one of the groups <math>\{2, 4\}, \{3, 9\}, \{2, 3, 6\},</math> or <math>\{2, 5, 10\}</math>. There are <math>2^7</math> 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 <math>2^7</math> subsets that contain 3 and 9, <math>2^6</math> subsets that contain 2, 3, and 6, and <math>2^6</math> subsets that contain 2, 5, and 10. The number of sets that contain one of the groups is: |
− | + | <cmath>2^7 + 2^7 + 2^6 + 2^6 = 384</cmath> | |
− | <math> | + | For sets that contain two of the groups, we have: |
− | + | <cmath>2^5 + 2^5 + 2^5 + 2^5 + 2^4 + 2^4 = 160</cmath> | |
− | + | For sets that contain three of the groups, we have: | |
− | < | + | <cmath>2^4 + 2^3 + 2^3 + 2^3 = 40</cmath> |
− | = | + | For sets that contain all of the groups, we have: |
− | + | <cmath>2^2 = 4</cmath> | |
− | + | By the principle of inclusion and exclusion, the number of product-free subsets is | |
− | <math> | + | <cmath>512 - (384 - 160 + 40 - 4) = \boxed{252}</cmath>. |
− | + | ||
− | + | ==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: | |
− | <math> | + | |
− | + | 1.) both 2 and 3 are not in <math>X</math>. Then there are <math>2^7=128</math> possible subsets for this case. | |
− | + | ||
− | <math> | + | 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}} |
Latest revision as of 22:58, 21 August 2020
Problem 12
Call a set product-free if there do not exist (not necessarily distinct) such that . For example, the empty set and the set are product-free, whereas the sets and are not product-free. Find the number of product-free subsets of the set .
Solution 1 (Casework)
We shall solve this problem by doing casework on the lowest element of the subset. Note that the number cannot be in the subset because . Let be a product-free set. If the lowest element of is , we consider the set . We see that 5 of these subsets can be a subset of (, , , , and the empty set). Now consider the set . We see that 3 of these subsets can be a subset of (, , and the empty set). Note that cannot be an element of , because is. Now consider the set . All four of these subsets can be a subset of . So if the smallest element of is , there are possible such sets.
If the smallest element of is , the only restriction we have is that is not in . This leaves us such sets.
If the smallest element of is not or , then can be any subset of , including the empty set. This gives us such subsets.
So our answer is .
Solution 2 (PIE)
We will consider the subsets that do not contain 1. A subset is product-free if and only if it does not contain one of the groups or . There are 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 subsets that contain 3 and 9, subsets that contain 2, 3, and 6, and subsets that contain 2, 5, and 10. The number of sets that contain one of the groups is: For sets that contain two of the groups, we have: For sets that contain three of the groups, we have: For sets that contain all of the groups, we have: By the principle of inclusion and exclusion, the number of product-free subsets is .
Solution 3
Let be a product-free subset, and note that 1 is not in . We consider four cases:
1.) both 2 and 3 are not in . Then there are possible subsets for this case.
2.) 2 is in , but 3 is not. Then 4 in not in , so there are subsets; however, there is a chance that 5 and 10 are both in , so there are subsets for this case.
3.) 2 is not in , but 3 is. Then, 9 is not in , so there are subsets for this case.
4.) 2 and 3 are both in . Then, 4, 6, and 9 are not in , so there are total subsets; however, there is a chance that 5 and 10 are both in , so there are subsets for this case.
Hence our answer is . -Stormersyle
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.