Difference between revisions of "2020 AMC 10B Problems/Problem 25"
(→Solution: Added a solution) |
(→Solution) |
||
Line 32: | Line 32: | ||
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>. | 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== | ||
+ | |||
+ | Begin 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 <math>D(96/f_1)</math>, since the product of <math>f_1 \cdot f_2</math>...<math> \cdot f_k</math> is 96 if and only if <math>f_1 \cdot x=96</math> and the product <math>x</math> has the properties that factors are greater than <math>1</math>, and order matters in counting the solutions, which is how <math>D</math> is defined. | ||
+ | |||
+ | For example, say the first factor is <math>2</math>, 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 possible starting factors, <math>D(96/f_a)</math> must be calculated and summed for all <math>f_a</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(4)+D(2)+1</math>. Instead of calculating D for the larger factors first, reduce <math>D(48)</math>, <math>D(32)</math>, and <math>D(24)</math> into sums of <math>D(m)</math> where <math>m<=16</math> to ease calculation. | ||
+ | |||
+ | Following the definition <math>D(n)=(</math>sums of <math>D(c))+1</math> where c takes on every divisor of n except for 1 and itself, the sum simplifies to <math>(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(4)+D(2)+1=\boxed{\textbf{(A) } 112}</math>. | ||
+ | |||
+ | ~monmath a.k.a Fmirza | ||
==See Also== | ==See Also== |
Revision as of 23:50, 7 February 2020
Problem
Let denote the number of ways of writing the positive integer
as a product
where
, 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
Note that . Since there are at most six not nexxessarily 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 2 in a manner that is 3-0-0, 2-1-0 or 1-1-1. A 3-0-0 split has
ways of happening (24-2-2 and symmetry; 2-3-16 and symmetry), a 2-1-0 split has
ways of happening (due to all being distinct) and a 1-1-1 split has
ways of happening (6-4-4 and symmetry) so in this case we have
ways.
: We have
as our baseline, and for the two other
's, we have a 2-0-0-0 or 1-1-0-0 split. The former grants us
ways (12-2-2-2 and symmetry and 3-8-2-2 and symmetry) and the latter grants us also
ways (6-4-2-2 and symmetry and 3-4-4-2 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 the rest must contain at least one factor of
. Next, 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 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
, since the product of
...
is 96 if and only if
and the product
has the properties that factors are greater than
, and order matters in counting the solutions, which is how
is defined.
For example, say the first factor is , the remaining numbers must multiply to
, so the number of ways the product can be written beginning with
is
. To add up all possible starting factors,
must be calculated and summed for all
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 definition sums of
where c takes on every divisor of n except for 1 and itself, the sum simplifies to
.
~monmath a.k.a Fmirza
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.