Mock AIME 1 2010 Problems/Problem 2
Problem
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 .
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 |