Difference between revisions of "2017 AIME I Problems/Problem 12"
(→Solution 2(PIE) (Should be explained in more detail)) |
m (→Solution 5) |
||
(18 intermediate revisions by 9 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> | |
− | The | + | 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> | |
− | = <math> | + | By the principle of inclusion and exclusion, the number of product-free subsets is |
− | + | <cmath>512 - 384 + 160 - 40 + 4 = \boxed{252}</cmath>. | |
− | = | + | |
− | = <math>2^4 | + | ==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>2^2</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. |
− | = 4 | + | |
− | <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 | ||
+ | |||
+ | ==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> | ||
+ | |||
+ | ==Solution 5== | ||
+ | |||
+ | Note that if any element <math>s\geq6</math> makes an invalid set, it must be <math>c</math> of <math>ab=c</math>. Otherwise, <math>ab\geq12>10</math> so no <math>ab=c</math> will suffice. Therefore, whether or not an element <math>s\geq6</math> depends only on the previous elements <math>1\leq\omega\leq5</math>. | ||
+ | |||
+ | First, if a set is product-free, it must never contain an element <math>\omega=1</math> or <math>1\cdot1=1</math>. | ||
+ | |||
+ | We do casework on the subset of <math>S\in{1,2,3,4,5}=s_1</math> to determine <math>S\in{6,7,8,9,10}=s_2</math> (There are only 12 to cover so we just list them out): | ||
+ | |||
+ | When it is empty, there are clearly no restrictions for <math>s_2</math> so there are <math>2^5=32</math> cases. | ||
+ | |||
+ | <math>s_1={2}, s_1={4}, s_1={5}</math> has no restrictions <math>s_2</math> so we get <math>2^5\cdot3=96</math> total cases. | ||
+ | |||
+ | <math>s_1=3</math> only cannot contain 9 so there are <math>2^4=16</math> cases. | ||
+ | |||
+ | <math>s_1={2, 5}; s_1={3, 4}; s_1={3, 5}</math> each have one restriction in <math>s_2</math> so there are <math>2^4\cdot3=48</math> ways. | ||
+ | |||
+ | <math>s_1={2, 3}</math> has 2 restrictions (6 and 9) so there are <math>2^3=8</math> ways. | ||
+ | |||
+ | <math>s_1={4, 5}</math> has no restrictions so there are <math>2^5=32</math> ways. | ||
+ | |||
+ | <math>s_1={2, 3, 5}</math> has 3 restrictions (6, 9, and 10) so there are <math>2^2=4</math> ways. | ||
+ | |||
+ | <math>s_1={3, 4, 5}</math> has 1 restriction so there are <math>2^4=16</math> cases. | ||
+ | |||
+ | Summing the numbers, we get <math>32+96+16+48+8+32+4+16=\boxed{252}</math>. | ||
+ | |||
+ | == Video Solution by OmegaLearn == | ||
+ | https://youtu.be/jRZQUv4hY_k?t=504 | ||
+ | |||
+ | ~ pi_is_3.14 | ||
==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 12:46, 24 January 2024
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
Solution 5
Note that if any element makes an invalid set, it must be
of
. Otherwise,
so no
will suffice. Therefore, whether or not an element
depends only on the previous elements
.
First, if a set is product-free, it must never contain an element or
.
We do casework on the subset of to determine
(There are only 12 to cover so we just list them out):
When it is empty, there are clearly no restrictions for so there are
cases.
has no restrictions
so we get
total cases.
only cannot contain 9 so there are
cases.
each have one restriction in
so there are
ways.
has 2 restrictions (6 and 9) so there are
ways.
has no restrictions so there are
ways.
has 3 restrictions (6, 9, and 10) so there are
ways.
has 1 restriction so there are
cases.
Summing the numbers, we get .
Video Solution by OmegaLearn
https://youtu.be/jRZQUv4hY_k?t=504
~ pi_is_3.14
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.