Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Found another solution)
(spelling error)
Line 159: Line 159:
 
First, you can see that <math>D(6)=3</math>, as given.
 
First, you can see that <math>D(6)=3</math>, as given.
 
As <math>96</math> is a multiple of 6, there is a likelihood there is a pattern.
 
As <math>96</math> is a multiple of 6, there is a likelihood there is a pattern.
−
Testing 12, which is 2 times 12 you get: <math>12</math> and a two pairing of each of <math>2\times 6, 3 \times 4</math> (flipping numbers matter)  and a three pairing of  <math> 2 \times 2 \times 3, \binom{3}{2}</math>  
+
Testing 12, which is 2 times 6 you get: <math>12</math> and a two pairing of each of <math>2\times 6, 3 \times 4</math> (flipping numbers matter)  and a three pairing of  <math> 2 \times 2 \times 3, \binom{3}{2}</math>  
 
This gives 8 terms.  
 
This gives 8 terms.  
 
Testing 24, you can get <math>24</math> by itself, and a two pairing of <math>2\times 12, 4 \times 6, 8 \times 3</math> (flipping numbers matter). There is a three pairing of <math>2\times 2 \times 6 , \binom{3}{2}</math>, a four pairing of <math>2 \times 2 \times 2 \times 3 , \binom{4}{3}</math> and a 6 pairing of <math>2\times 4 \times 3 ,3!</math>, in total you get 20.
 
Testing 24, you can get <math>24</math> by itself, and a two pairing of <math>2\times 12, 4 \times 6, 8 \times 3</math> (flipping numbers matter). There is a three pairing of <math>2\times 2 \times 6 , \binom{3}{2}</math>, a four pairing of <math>2 \times 2 \times 2 \times 3 , \binom{4}{3}</math> and a 6 pairing of <math>2\times 4 \times 3 ,3!</math>, in total you get 20.

Revision as of 15:12, 25 August 2022

The following problem is from both the 2020 AMC 10B #25 and 2020 AMC 12B #24, so both problems redirect to this page.

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 1

Note that $96 = 2^5 \cdot 3$. Since there are at most six not necessarily 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=\boxed{\textbf{(A) } 112}$.

~kevinmathz

Solution 2

As before, note that $96=2^5\cdot3$, and we need to consider 6 different cases, one for each possible value of $k$, 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 $k$ factors. First, the factorization needs to contain one factor that is itself a multiple of $3$. There are $k$ to choose from. That leaves $k-1$ slots left to fill, each of which must contain at least one factor of $2$. Once we have filled in a $2$ to each of the remaining slots, we're left with $5-(k-1)=6-k$ twos.

Consider the remaining $6-k$ factors of $2$ left to assign to the $k$ factors. Using stars and bars, the number of ways to do this is: \[{{(6-k)+k-1}\choose{6-k}}={5\choose{6-k}}\] This makes $k{5\choose{6-k}}$ possibilities for each k.

To obtain the total number of factorizations, add all possible values for k: \[\sum_{k=1}^6 k{5\choose{6-k}}=1+10+30+40+25+6=\boxed{\textbf{(A) } \text{112}}.\]

Solution 3

Begin by examining $f_1$. $f_1$ can take on any value that is a factor of $96$ except $1$. For each choice of $f_1$, the resulting $f_2...f_k$ must have a product of $96/f_1$. This means the number of ways the rest $f_a$, $1<a<=k$ can be written by the scheme stated in the problem for each $f_1$ is equal to $D(96/f_1)$, since the product of $f_2 \cdot f_3... \cdot f_k=x$ is counted as one valid product if and only if $f_1 \cdot x=96$, the product $x$ has the properties that factors are greater than $1$, and differently ordered products are counted separately.

For example, say the first factor is $2$. Then, the remaining numbers must multiply to $48$, so the number of ways the product can be written beginning with $2$ is $D(48)$. To add up all the number of solutions for every possible starting factor, $D(96/f_1)$ must be calculated and summed for all possible $f_1$, except $96$ and $1$, since a single $1$ is not counted according to the problem statement. The $96$ however, is counted, but only results in $1$ possibility, the first and only factor being $96$. This means

$D(96)=D(48)+D(32)+D(24)+D(16)+D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+1$.

Instead of calculating D for the larger factors first, reduce $D(48)$, $D(32)$, and $D(24)$ into sums of $D(m)$ where $m<=16$ to ease calculation. Following the recursive definition $D(n)=($sums of $D(c))+1$ where c takes on every divisor of n except for 1 and itself, the sum simplifies to

$D(96)=(D(24)+D(16)+D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+1)$ +$(D(16)+D(8)+D(4)+D(2)+1)+D(24)+D(16)+D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+1.$

$D(24)=D(12)+D(8)+D(6)+D(4)+D(3)+D(2)+1$, so the sum further simplifies to

$D(96)=3D(16)+4D(12)+5D(8)+4D(6)+5D(4)+4D(3)+5D(2)+5$, after combining terms. From quick casework,

$D(16)=8, D(12)=8, D(8)=4, D(6)=3, D(4)=2, D(3)=1$ and $D(2)=1$. Substituting these values into the expression above,

$D(96)=3 \cdot 8+4 \cdot 8+5 \cdot 4+4 \cdot 3+5 \cdot 2+4 \cdot 1+5 \cdot 1+5=\boxed{\textbf{(A) } 112}$.

~monmath a.k.a Fmirza

Solution 4

Note that $96 = 3 \cdot 2^5$, and that $D$ of a perfect power of a prime is relatively easy to calculate. Also note that you can find $D(96)$ from $D(32)$ by simply totaling the number of ways there are to insert a $3$ into a set of numbers that multiply to $32$.

First, calculate $D(32)$. Since $32 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2$, all you have to do was find the number of ways to divide the $2$'s into groups, such that each group has at least one $2$. By stars and bars, this results in $1$ way with five terms, $4$ ways with four terms, $6$ ways with three terms, $4$ ways with two terms, and $1$ way with one term. (The total, $16$, is not needed for the remaining calculations.)

Then, to get $D(96)$, in each possible $D(32)$ sequence, insert a $3$ somewhere in it, either by placing it somewhere next to the original numbers (in one of $n+1$ ways, where $n$ is the number of terms in the $D(32)$ sequence), or by multiplying one of the numbers by $3$ (in one of $n$ ways). There are $2+1=3$ ways to do this with one term, $3+2=5$ with two, $7$ with three, $9$ with four, and $11$ with five.

The resulting number of possible sequences is $3 \cdot 1 + 5 \cdot 4 + 7 \cdot 6 + 9 \cdot 4 + 11 \cdot 1 = \boxed{\textbf{(A) }112}$. ~emerald_block

Solution 5 (Minimal Casework)

Consider the arrangement of the prime factors of 96 in a line $(2,2, 2, 2, 2, 3)$. An arrangement of factors can be created by placing "dividers" to group primes. For example, $(2, 2, |, 2, 2, 2, |, 3)$ is equivalent to the arrangement $4 \cdot 8 \cdot 3$. Because there are $6$ ways to order the prime factors, and $2^5$ ways to place dividers, this gives us an initial $6 \cdot 2^5$ ways to arrange divisors.

However, through this method, we overcount cases where $3$ is combined with another factor. For example, the arrangement $4 \cdot 6 \cdot 4$ can be written as $(2, 2, |, 2, 3, |, 2, 2)$ or $(2, 2, |, 3, 2, |, 2, 2)$. Precisely, we double count any case with $6$ as a factor, triple count any case with $12$, quadruple count any case with $24$, etc.

Now, consider all cases where $3$ must be grouped with at least one $2$. This can be expressed in the same "line" format as $(2, 2, 2, 2, 6)$, where dividers can again be placed to group divisors. In this case, there are $5$ ways to order divisors, and $2^4$ ways to place dividers, so we have an $5 \cdot 2^4$ possible sequences for this case. Notice that in this format, we double count cases where $12$ is a factor, we triple count cases where $24$ is a factor, etc. Precisely, for any case counted $n$ times in the first step, it is counted $n - 1$ times in this step. Thus, if we subtract, we count each case exactly once.

So, we get:

$6 \cdot 2^5 - 5 \cdot 2^4 = \boxed{\textbf{(A) }112}$. ~hdai1122

Solution 6 (Another Fast Way)

First we factor $32$ into $m$ numbers $g_1, \cdots, g_m$ where $g_i>1,i=1,\ldots,m$. By applying stars and bars there are $\binom{5-1}{m-1}$ ways. Then we can either insert $3$ into each of the $m+1$ spaces between (or beyond) $g_i$'s, or multiply it to one of the $g_i$'s, a total of $2m+1$ ways. Hence the answer to the problem is

\[\sum_{m=1}^5 (2m+1)\binom{5-1}{m-1} = \sum_{n=0}^4 (2n+3) \binom{4}{n} = 8\sum_{n=0}^4 \frac{n}{4} \binom{4}{n} + 3 \sum_{n=0}^4 \binom{4}{n} = 8 \sum_{n=0}^4 \binom{3}{n-1} + 3\sum_{n=0}^4 \binom{4}{n} = 8 \cdot 2^3 + 3\cdot 2^4 = \boxed{\textbf{(A) }112}.\]

~ asops

Solution 7 (Integer Partition)

Note that $96 = 2^5 \cdot 3$. $D(n)$ depends on dividing $2^5$ into different terms, which is the integer partition of $5$.

Divide $96$ into $1$ term:

There is only one way. $\underline{\textbf{1}}$


Divide $96$ into $2$ terms: 

Case $1$: $3$ is alone
$(2^5,3)$ has ${\textbf{2}}$ different arrangements.

Case $2$: $3$ is with $2^n$
$5 = 1 + 4 = 2 + 3$. For $(2, 2^4)$ and $(2^2, 2^3)$, $3$ can be with any term from the $2$ tuples, and the number of  arrangement of the $2$ terms is $2$. $2 \cdot 2 \cdot 2 = {\textbf{8}}$

$2 + 8 = \underline{\textbf{10}}$


Divide $96$ into $3$ terms: 

Case $1$: $3$ is alone
$5 = 2 + 3 = 1 + 4$. For $(2^2, 2^3, 3)$ and $(2, 2^4, 3)$, there are $3!$ arrangements each. $2 \cdot 3! = {\textbf{12}}$

Case $2$: $3$ is with $2^n$
$5 = 1 + 1 + 3 = 1 + 2 + 2$. For $(2, 2, 2^3)$ and $(2, 2^2, 2^2)$, $3$ can be with any term from the $2$ tuples. If $3$ is with $2^3$ for the first tuple, or $2$ for the second tuple, the number of arrangements is $3$ for each. If $3$ is with $2$ for the first tuple, or $2^2$ for the second tuple, the number of arrangements is $6$ for each. $2 \cdot 3 + 2 \cdot 6 = {\textbf{18}}$

$12 + 18 = \underline{\textbf{30}}$


Divide $96$ into $4$ terms: 

Case $1$: $3$ is alone
$5 = 1 + 1 + 3 = 1 + 2 + 2$. For $(2, 2, 2^3, 3)$ and $(2, 2^2, 2^2, 3)$, there are $\frac{4!}{2!}$ arrangements each. $2 \cdot \frac{4!}{2!} = {\textbf{24}}$

Case $2$: $3$ is with $2^n$
$5 = 1 + 1 + 1 + 2$. For $(2, 2, 2, 2^2)$, $3$ can be with any term from the tuple. If $3$ is with $2^2$, the number of arrangements is $\frac{4!}{3!}$. If $3$ is with $2$, the number of arrangements is $\frac{4!}{2!}$.
$\frac{4!}{3!} + \frac{4!}{2!} = {\textbf{16}}$

$24 + 16 = \underline{\textbf{40}}$


Divide $96$ into $5$ terms:

When dividing $5$ into $5$ parts there are $2$ cases. 

Case $1$: $3$ is alone
$5 = 1 + 1 + 1 + 2$. For $(2, 2, 2, 2^2, 3)$, there are $\frac{5!}{3!}$ arrangements. $\frac{5!}{3!} = {\textbf{20}}$

Case $2$: $3$ is with $2^n$
$5 = 1 + 1 + 1 + 1 + 1$. For $(2, 2, 2, 2, 2)$, $3$ can only be with $2$. The number of arrangements is $\frac{5!}{4!} = \textbf{5}$

$20 + 5 = \underline{\textbf{25}}$


Divide $96$ into $6$ terms:

$5 = 1 + 1 + 1 + 1 + 1$. The number of arrangements of $(2, 2, 2, 2, 2, 3)$ is $\frac{6!}{5!} = \underline{\textbf{6}}$


$1 + 10 + 30 + 40 + 25 + 6 = \boxed{\textbf{(A) }112}$

~isabelchen

Solution 8 (Lucky Pattern Finding)

First, you can see that $D(6)=3$, as given. As $96$ is a multiple of 6, there is a likelihood there is a pattern. Testing 12, which is 2 times 6 you get: $12$ and a two pairing of each of $2\times 6, 3 \times 4$ (flipping numbers matter) and a three pairing of $2 \times 2 \times 3, \binom{3}{2}$ This gives 8 terms. Testing 24, you can get $24$ by itself, and a two pairing of $2\times 12, 4 \times 6, 8 \times 3$ (flipping numbers matter). There is a three pairing of $2\times 2 \times 6 , \binom{3}{2}$, a four pairing of $2 \times 2 \times 2 \times 3 , \binom{4}{3}$ and a 6 pairing of $2\times 4 \times 3 ,3!$, in total you get 20. If 3 is written as $2^0\times 3$, 8 is written as $2^1 \times 4$, 20 written as $2^2 \times 5$, then you can see how $D(a\times b^c)= 2^c \times (c+3)$ when a and b are distinct prime numbers. Continuing this pattern you get $D(48)=2^3 \times 6, D(96)=2^4 \times 7$ which means $D(96)=112$ so $\boxed{\textbf{(A) }112}$

~ryk

Video Solutions

Video Solution 1

https://youtu.be/8WrdYLw9_ns?t=1444 - Quicker Way

~ pi_is_3.14

Video Solution 2

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
2020 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 23 		Followed by
Problem 25
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 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10B_Problems/Problem_25&oldid=177486"