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}$ .

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

Page

Toolbox

Search

Mock AIME 1 2010 Problems/Problem 2

Problem

Solution

See Also