Difference between revisions of "2020 AMC 10B Problems/Problem 25"

(Solution)
(Solution)
Line 7: Line 7:
 
==Solution==
 
==Solution==
  
Note that <math>96 = 2^5 \cdot 3</math>. Since there are at most six not nexxessarily distinct factors <math>>1</math> multiplying to <math>96</math>, we have six cases: <math>k=1, 2, ..., 6.</math>
+
Note that <math>96 = 2^5 \cdot 3</math>. Since there are at most six not nexxessarily 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.
 +
 
  
 
<math>k=1</math>: We see that there is <math>1</math> way, merely <math>96</math>.
 
<math>k=1</math>: We see that there is <math>1</math> way, merely <math>96</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=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 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=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 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=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.
 +
 
<math>k=6</math>: We have <math>3, 2, 2, 2, 2, 2</math> and symmetry and no more twos to multiply, so by symmetry, we have <math>6</math> ways.
 
<math>k=6</math>: We have <math>3, 2, 2, 2, 2, 2</math> and symmetry and no more twos to multiply, so by symmetry, we have <math>6</math> ways.
 +
  
 
Thus, adding, we have <math>1+10+30+40+25+6=\textbf{(A) } 112</math>.
 
Thus, adding, we have <math>1+10+30+40+25+6=\textbf{(A) } 112</math>.

Revision as of 23:37, 7 February 2020

Problem

Let $D(n)$ denote the number of ways of writing the positive integer $n$ as a product\[n = f_1\cdot f_2\cdots f_k,\]where $k\ge1$, the $f_i$ are integers strictly greater than $1$, 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 $6$ can be written as $6$, $2\cdot 3$, and $3\cdot2$, so $D(6) = 3$. What is $D(96)$?

$\textbf{(A) } 112 \qquad\textbf{(B) } 128 \qquad\textbf{(C) } 144 \qquad\textbf{(D) } 172 \qquad\textbf{(E) } 184$

Solution

Note that $96 = 2^5 \cdot 3$. Since there are at most six not nexxessarily distinct factors $>1$ multiplying to $96$, we have six cases: $k=1, 2, ..., 6.$ Now we look at each of the six cases.


$k=1$: We see that there is $1$ way, merely $96$.

$k=2$: This way, we have the $3$ in one slot and $2$ in another, and symmetry. The four other $2$'s leave us with $5$ ways and symmetry doubles us so we have $10$.

$k=3$: We have $3, 2, 2$ as our baseline. We need to multiply by $2$ in $3$ 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 $6 + 3 = 9$ ways of happening (24-2-2 and symmetry; 2-3-16 and symmetry), a 2-1-0 split has $6 \cdot 3 = 18$ ways of happening (due to all being distinct) and a 1-1-1 split has $3$ ways of happening (6-4-4 and symmetry) so in this case we have $9+18+3=30$ ways.

$k=4$: We have $3, 2, 2, 2$ as our baseline, and for the two other $2$'s, we have a 2-0-0-0 or 1-1-0-0 split. The former grants us $4+12=16$ ways (12-2-2-2 and symmetry and 3-8-2-2 and symmetry) and the latter grants us also $12+12=24$ ways (6-4-2-2 and symmetry and 3-4-4-2 and symmetry) for a total of $16+24=40$ ways.

$k=5$: We have $3, 2, 2, 2, 2$ as our baseline and one place to put the last two: on another two or on the three. On the three gives us $5$ ways due to symmetry and on another two gives us $5 \cdot 4 = 20$ ways due to symmetry. Thus, we have $5+20=25$ ways.

$k=6$: We have $3, 2, 2, 2, 2, 2$ and symmetry and no more twos to multiply, so by symmetry, we have $6$ ways.


Thus, adding, we have $1+10+30+40+25+6=\textbf{(A) } 112$.

~kevinmathz

See Also

2020 AMC 10B (ProblemsAnswer KeyResources)
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. AMC logo.png