Difference between revisions of "2017 AIME I Problems/Problem 12"
Thebeast5520 (talk | contribs) |
|||
(14 intermediate revisions by 7 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> | |
− | < | + | 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 | ||
+ | <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: | ||
+ | |||
+ | 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 | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | First, ignore 7 as it does not affect any of the other numbers; we can multiply by 2 later (its either in or out). | ||
+ | |||
+ | Next, we do casework based on whether 2, 3, or 5 are in the set (<math>2^3 = 8</math> quick cases). For each of the cases, the numbers will be of two types --- | ||
+ | |||
+ | 1. They cannot be in the set because they form a product | ||
+ | |||
+ | 2. Whether we add the number to the set or not, it does not affect the rest of the numbers. These numbers simply add a factor of 2 to the case. | ||
+ | |||
+ | For example, in the case where all three are present, we can see that <math>4, 6, 9, 10</math> are of type 1. However, <math>8</math> is of type 2. Therefore this case contributes 2. | ||
+ | |||
+ | Summing over the 8 cases we get <math>2 + 4 + 8 + 16 + 16 + 16 + 32 + 32 = 126.</math> Multiplying by <math>2</math> because of the <math>7</math> gives <math>252.</math> | ||
+ | |||
==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 19:41, 15 August 2021
Contents
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
Solution 4
First, ignore 7 as it does not affect any of the other numbers; we can multiply by 2 later (its either in or out).
Next, we do casework based on whether 2, 3, or 5 are in the set ( quick cases). For each of the cases, the numbers will be of two types ---
1. They cannot be in the set because they form a product
2. Whether we add the number to the set or not, it does not affect the rest of the numbers. These numbers simply add a factor of 2 to the case.
For example, in the case where all three are present, we can see that are of type 1. However, is of type 2. Therefore this case contributes 2.
Summing over the 8 cases we get Multiplying by because of the gives
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.