Difference between revisions of "2020 AMC 10B Problems/Problem 25"
(→Solution) |
Ritvikaops (talk | contribs) m (→Video Solution) |
||
(23 intermediate revisions by 13 users not shown) | |||
Line 5: | Line 5: | ||
<math>\textbf{(A) } 112 \qquad\textbf{(B) } 128 \qquad\textbf{(C) } 144 \qquad\textbf{(D) } 172 \qquad\textbf{(E) } 184</math> | <math>\textbf{(A) } 112 \qquad\textbf{(B) } 128 \qquad\textbf{(C) } 144 \qquad\textbf{(D) } 172 \qquad\textbf{(E) } 184</math> | ||
− | ==Solution== | + | ==Solution 1== |
Note that <math>96 = 2^5 \cdot 3</math>. Since there are at most six not necessarily distinct factors <math>>1</math> multiplying to <math>96</math>, we have six cases: <math>k=1, 2, ..., 6.</math> Now we look at each of the six cases. | Note that <math>96 = 2^5 \cdot 3</math>. Since there are at most six not necessarily distinct factors <math>>1</math> multiplying to <math>96</math>, we have six cases: <math>k=1, 2, ..., 6.</math> Now we look at each of the six cases. | ||
Line 14: | Line 14: | ||
<math>k=2</math>: This way, we have the <math>3</math> in one slot and <math>2</math> in another, and symmetry. The four other <math>2</math>'s leave us with <math>5</math> ways and symmetry doubles us so we have <math>10</math>. | <math>k=2</math>: This way, we have the <math>3</math> in one slot and <math>2</math> in another, and symmetry. The four other <math>2</math>'s leave us with <math>5</math> ways and symmetry doubles us so we have <math>10</math>. | ||
− | <math>k=3</math>: We have <math>3, 2, 2</math> as our baseline. We need to multiply by <math>2</math> in <math>3</math> places, and see that we can split the remaining three powers of 2 in a manner that is 3-0-0, 2-1-0 or 1-1-1. A 3-0-0 split has <math>6 + 3 = 9</math> ways of happening (24-2-2 and symmetry; 2-3-16 and symmetry), a 2-1-0 split has <math>6 \cdot 3 = 18</math> ways of happening (due to all being distinct) and a 1-1-1 split has <math>3</math> ways of happening (6-4-4 and symmetry) so in this case we have <math>9+18+3=30</math> ways. | + | <math>k=3</math>: We have <math>3, 2, 2</math> as our baseline. We need to multiply by <math>2</math> in <math>3</math> places, and see that we can split the remaining three powers of <math>2</math> in a manner that is <math>3-0-0</math>, <math>2-1-0</math> or <math>1-1-1</math>. A <math>3-0-0</math> split has <math>6 + 3 = 9</math> ways of happening (<math>24-2-2</math> and symmetry; <math>2-3-16</math> and symmetry), a <math>2-1-0</math> split has <math>6 \cdot 3 = 18</math> ways of happening (due to all being distinct) and a <math>1-1-1</math> split has <math>3</math> ways of happening (<math>6-4-4</math> and symmetry) so in this case we have <math>9+18+3=30</math> ways. |
− | <math>k=4</math>: We have <math>3, 2, 2, 2</math> as our baseline, and for the two other <math>2</math>'s, we have a 2-0-0-0 or 1-1-0-0 split. The former grants us <math>4+12=16</math> ways (12-2-2-2 and symmetry and 3-8-2-2 and symmetry) and the latter grants us also <math>12+12=24</math> ways (6-4-2-2 and symmetry and 3-4-4-2 and symmetry) for a total of <math>16+24=40</math> ways. | + | <math>k=4</math>: We have <math>3, 2, 2, 2</math> as our baseline, and for the two other <math>2</math>'s, we have a <math>2-0-0-0</math> or <math>1-1-0-0</math> split. The former grants us <math>4+12=16</math> ways (<math>12-2-2-2</math> and symmetry and <math>3-8-2-2</math> and symmetry) and the latter grants us also <math>12+12=24</math> ways (<math>6-4-2-2</math> and symmetry and <math>3-4-4-2</math> and symmetry) for a total of <math>16+24=40</math> ways. |
<math>k=5</math>: We have <math>3, 2, 2, 2, 2</math> as our baseline and one place to put the last two: on another two or on the three. On the three gives us <math>5</math> ways due to symmetry and on another two gives us <math>5 \cdot 4 = 20</math> ways due to symmetry. Thus, we have <math>5+20=25</math> ways. | <math>k=5</math>: We have <math>3, 2, 2, 2, 2</math> as our baseline and one place to put the last two: on another two or on the three. On the three gives us <math>5</math> ways due to symmetry and on another two gives us <math>5 \cdot 4 = 20</math> ways due to symmetry. Thus, we have <math>5+20=25</math> ways. | ||
Line 29: | Line 29: | ||
==Solution 2== | ==Solution 2== | ||
− | As before, note that <math>96=2^5\cdot3</math>, and we need to consider 6 different cases, one for each possible value of <math>k</math>, the number of factors in our factorization. However, instead of looking at each individually, find a general form for the number of possible factorizations with <math>k</math> factors. First, the factorization needs to contain one factor that is itself a multiple of <math>3</math>, and there are <math>k</math> to choose from, and | + | As before, note that <math>96=2^5\cdot3</math>, and we need to consider 6 different cases, one for each possible value of <math>k</math>, the number of factors in our factorization. However, instead of looking at each individually, find a general form for the number of possible factorizations with <math>k</math> factors. First, the factorization needs to contain one factor that is itself a multiple of <math>3</math>, and there are <math>k</math> to choose from, and that leaves <math>k-1</math> slots left to fill, each of which must contain at least one factor of <math>2</math>. Once we have filled in a two to each of the remainder slots, we're left with <math>5-(k-1)=6-k</math> twos. |
− | To obtain the total number of factorizations, add all possible values for k: <cmath>\sum_{k=1}^6 k{5\choose{6-k}}=1+10+30+40+25+6=\boxed{\textbf{(A) } \text{112}}</cmath> | + | Consider the remaining <math>6-k</math> factors of <math>2</math> left to assign to the <math>k</math> factors. Using stars and bars, the number of ways to do this is: |
+ | <cmath>{{(6-k)+(k-1)}\choose{6-k}}={5\choose{6-k}}</cmath> This makes <math>k{5\choose{6-k}}</math> possibilities for each k. | ||
+ | |||
+ | To obtain the total number of factorizations, add all possible values for k: <cmath>\sum_{k=1}^6 k{5\choose{6-k}}=1+10+30+40+25+6=\boxed{\textbf{(A) } \text{112}}.</cmath> | ||
==Solution 3== | ==Solution 3== | ||
− | Begin by examining <math>f_1</math>. <math>f_1</math> can take on any value that is a factor of <math>96</math> except <math>1</math>. For each choice of <math>f_1</math>, the resulting <math>f_2...f_k</math> must have a product of <math>96/f_1</math>. This means the number of ways the rest <math>f_a</math> <math>1<a<=k</math> can be written by the scheme stated in the problem for each <math>f_1</math> is equal to <math>D(96/f_1)</math>, since the product of <math>f_2 \cdot f_3 | + | Begin by examining <math>f_1</math>. <math>f_1</math> can take on any value that is a factor of <math>96</math> except <math>1</math>. For each choice of <math>f_1</math>, the resulting <math>f_2...f_k</math> must have a product of <math>96/f_1</math>. This means the number of ways the rest <math>f_a</math>, <math>1<a<=k</math> can be written by the scheme stated in the problem for each <math>f_1</math> is equal to <math>D(96/f_1)</math>, since the product of <math>f_2 \cdot f_3... \cdot f_k=x</math> is counted as one valid product if and only if <math>f_1 \cdot x=96</math>, the product <math>x</math> has the properties that factors are greater than <math>1</math>, and differently ordered products are counted separately. |
− | For example, say the first factor is <math>2</math>. Then, the remaining numbers must multiply to <math>48</math>, so the number of ways the product can be written beginning with <math>2</math> is <math>D(48)</math>. To add up all the number of solutions for every possible starting factor, <math>D(96/ | + | For example, say the first factor is <math>2</math>. Then, the remaining numbers must multiply to <math>48</math>, so the number of ways the product can be written beginning with <math>2</math> is <math>D(48)</math>. To add up all the number of solutions for every possible starting factor, <math>D(96/f_1)</math> must be calculated and summed for all possible <math>f_1</math>, except <math>96</math> and <math>1</math>, since a single <math>1</math> is not counted according to the problem statement. The <math>96</math> however, is counted, but only results in <math>1</math> possibility, the first and only factor being <math>96</math>. This means |
<math>D(96)=D(48)+D(32)+D(24)+D(16)+D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+1</math>. | <math>D(96)=D(48)+D(32)+D(24)+D(16)+D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+1</math>. | ||
Line 64: | Line 67: | ||
The resulting number of possible sequences is <math>3 \cdot 1 + 5 \cdot 4 + 7 \cdot 6 + 9 \cdot 4 + 11 \cdot 1 = \boxed{\textbf{(A) }112}</math>. ~[[User:emerald_block|emerald_block]] | The resulting number of possible sequences is <math>3 \cdot 1 + 5 \cdot 4 + 7 \cdot 6 + 9 \cdot 4 + 11 \cdot 1 = \boxed{\textbf{(A) }112}</math>. ~[[User:emerald_block|emerald_block]] | ||
+ | |||
+ | == Video Solution == | ||
+ | https://youtu.be/8WrdYLw9_ns?t=1444 - Quicker Way | ||
+ | |||
+ | ~ pi_is_3.14 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=977F9lBb37E&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=11&t=0s ~ MathEx | ||
==See Also== | ==See Also== |
Latest revision as of 00:31, 21 January 2021
Contents
Problem
Let denote the number of ways of writing the positive integer as a productwhere , the are integers strictly greater than , and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number can be written as , , and , so . What is ?
Solution 1
Note that . Since there are at most six not necessarily distinct factors multiplying to , we have six cases: Now we look at each of the six cases.
: We see that there is way, merely .
: This way, we have the in one slot and in another, and symmetry. The four other 's leave us with ways and symmetry doubles us so we have .
: We have as our baseline. We need to multiply by in places, and see that we can split the remaining three powers of in a manner that is , or . A split has ways of happening ( and symmetry; and symmetry), a split has ways of happening (due to all being distinct) and a split has ways of happening ( and symmetry) so in this case we have ways.
: We have as our baseline, and for the two other 's, we have a or split. The former grants us ways ( and symmetry and and symmetry) and the latter grants us also ways ( and symmetry and and symmetry) for a total of ways.
: We have as our baseline and one place to put the last two: on another two or on the three. On the three gives us ways due to symmetry and on another two gives us ways due to symmetry. Thus, we have ways.
: We have and symmetry and no more twos to multiply, so by symmetry, we have ways.
Thus, adding, we have .
~kevinmathz
Solution 2
As before, note that , and we need to consider 6 different cases, one for each possible value of , the number of factors in our factorization. However, instead of looking at each individually, find a general form for the number of possible factorizations with factors. First, the factorization needs to contain one factor that is itself a multiple of , and there are to choose from, and that leaves slots left to fill, each of which must contain at least one factor of . Once we have filled in a two to each of the remainder slots, we're left with twos.
Consider the remaining factors of left to assign to the factors. Using stars and bars, the number of ways to do this is: This makes possibilities for each k.
To obtain the total number of factorizations, add all possible values for k:
Solution 3
Begin by examining . can take on any value that is a factor of except . For each choice of , the resulting must have a product of . This means the number of ways the rest , can be written by the scheme stated in the problem for each is equal to , since the product of is counted as one valid product if and only if , the product has the properties that factors are greater than , and differently ordered products are counted separately.
For example, say the first factor is . Then, the remaining numbers must multiply to , so the number of ways the product can be written beginning with is . To add up all the number of solutions for every possible starting factor, must be calculated and summed for all possible , except and , since a single is not counted according to the problem statement. The however, is counted, but only results in possibility, the first and only factor being . This means
.
Instead of calculating D for the larger factors first, reduce , , and into sums of where to ease calculation. Following the recursive definition sums of where c takes on every divisor of n except for 1 and itself, the sum simplifies to
+
, so the sum further simplifies to
, after combining terms. From quick casework,
and . Substituting these values into the expression above,
.
~monmath a.k.a Fmirza
Solution 4
Note that , and that of a perfect power of a prime is relatively easy to calculate. Also note that you can find from by simply totaling the number of ways there are to insert a into a set of numbers that multiply to .
First, calculate . Since , all you have to do was find the number of ways to divide the 's into groups, such that each group has at least one . By stars and bars, this results in way with five terms, ways with four terms, ways with three terms, ways with two terms, and way with one term. (The total, , is not needed for the remaining calculations.)
Then, to get , in each possible sequence, insert a somewhere in it, either by placing it somewhere next to the original numbers (in one of ways, where is the number of terms in the sequence), or by multiplying one of the numbers by (in one of ways). There are ways to do this with one term, with two, with three, with four, and with five.
The resulting number of possible sequences is . ~emerald_block
Video Solution
https://youtu.be/8WrdYLw9_ns?t=1444 - Quicker Way
~ pi_is_3.14
Video Solution
https://www.youtube.com/watch?v=977F9lBb37E&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=11&t=0s ~ MathEx
See Also
2020 AMC 10B (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AMC 10 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.