Mock AIME 1 2010 Problems/Problem 2

Problem

Find the last three digits of the number of 7-tuples of positive integers $(a_1, a_2, a_3, a_4, a_5, a_6, a_7)$ such that $a_1 \, | \, a_2 \, | \, a_3 \, | \, a_4 \, | \, a_5 \, | \, a_6 \, | \, a_7 \, | \, 6468$, that is, $a_1$ divides $a_2$, $a_2$ divides $a_3$, $a_3$ divides $a_4$, $a_4$ divides $a_5$, $a_5$ divides $a_6$, $a_6$ divides $a_7$, and $a_7$ divides $6468$.

Solution

Note that $6468=2^2\cdot3\cdot7^2\cdot11$. Each successive term in the sequence $a_1,a_2,\ldots,a_7$ 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 $2$s, one $3$, two $7$s, and one $11$ into seven boxes. We do not necessarily need to use all of the factors (for example, all of the terms could be $1$), so we can think of this exclusion as adding an eighth box to our problem. For each of the singular prime factors, there are $\tbinom81=8$ ways to arrange them into the $8$ boxes. Because there are two such factors ($3$ and $11$), together they have $8^2$ possibilities. For each squared prime factor, they have $\tbinom82=28$ ways if they are not in the same box and $\tbinom81=8$ ways if they are. Because there are two such factors ($2$ and $7$), together they have $(28+8)^2=36^2$ possibilities. Thus, the total number of arrangements is $36^2\cdot8^2=288^2=82,944$, so our answer is $\boxed{944}$.

See Also

Mock AIME 1 2010 (Problems, Source)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15