Difference between revisions of "Mock AIME 1 2010 Problems/Problem 2"
(created solution page) |
(→Solution) |
||
Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
− | <math>\boxed{944}</math>. | + | Note that <math>6468=2^2\cdot3\cdot7^2\cdot11</math>. Each successive term in the sequence <math>a_1,a_2,\ldots,a_7</math> must have the same amount or more factors than the term before it. Thus, once a (potentially repeated) prime factor is "introduced," every subsequent term must also include that prime factor. Therefore, we can think of the problem as the number of ways to sort two <math>2</math>s, one <math>3</math>, two <math>7</math>s, and one <math>11</math> into seven boxes. We do not necessarily need to use all of the factors (for example, all of the terms could be <math>1</math>), so we can think of this exclusion as adding an eighth box to our problem. For each of the singular prime factors, there are <math>\tbinom81=8</math> ways to arrange them into the <math>8</math> boxes. Because there are two such factors (<math>3</math> and <math>11</math>), together they have <math>8^2</math> possibilities. For each squared prime factor, they have <math>\tbinom82=28</math> ways if they are not in the same box and <math>\tbinom81=8</math> ways if they are. Because there are two such factors (<math>2</math> and <math>7</math>), together they have <math>(28+8)^2=36^2</math> possibilities. Thus, the total number of arrangements is <math>36^2\cdot8^2=288^2=82,944</math>, so our answer is <math>\boxed{944}</math>. |
== See Also == | == See Also == |
Revision as of 07:33, 2 August 2024
Problem 2
Find the last three digits of the number of 7-tuples of positive integers such that
, that is,
divides
,
divides
,
divides
,
divides
,
divides
,
divides
, and
divides
.
Solution
Note that . Each successive term in the sequence
must have the same amount or more factors than the term before it. Thus, once a (potentially repeated) prime factor is "introduced," every subsequent term must also include that prime factor. Therefore, we can think of the problem as the number of ways to sort two
s, one
, two
s, and one
into seven boxes. We do not necessarily need to use all of the factors (for example, all of the terms could be
), so we can think of this exclusion as adding an eighth box to our problem. For each of the singular prime factors, there are
ways to arrange them into the
boxes. Because there are two such factors (
and
), together they have
possibilities. For each squared prime factor, they have
ways if they are not in the same box and
ways if they are. Because there are two such factors (
and
), together they have
possibilities. Thus, the total number of arrangements is
, so our answer is
.