Difference between revisions of "Mock AIME 1 2010 Problems/Problem 2"
m (better see also) |
m (category) |
||
| Line 7: | Line 7: | ||
== See Also == | == See Also == | ||
{{Mock AIME box|year=2010|n=1|num-b=1|num-a=3}} | {{Mock AIME box|year=2010|n=1|num-b=1|num-a=3}} | ||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
Latest revision as of 08:46, 2 August 2024
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 | ||
