Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 1 2010 Problems/Problem 2"

(→‎Solution)
m
Line 1: Line 1:
−
== Problem 2 ==
+
== Problem ==
 
Find the last three digits of the number of 7-tuples of positive integers <math>(a_1, a_2, a_3, a_4, a_5, a_6, a_7)</math> such that <math>a_1 \, | \, a_2 \, | \, a_3 \, | \, a_4 \, | \, a_5 \, | \, a_6 \, | \, a_7 \, | \, 6468</math>, that is, <math>a_1</math> divides <math>a_2</math>, <math>a_2</math> divides <math>a_3</math>, <math>a_3</math> divides <math>a_4</math>, <math>a_4</math> divides <math>a_5</math>, <math>a_5</math> divides <math>a_6</math>, <math>a_6</math> divides <math>a_7</math>, and <math>a_7</math> divides <math>6468</math>.
 
Find the last three digits of the number of 7-tuples of positive integers <math>(a_1, a_2, a_3, a_4, a_5, a_6, a_7)</math> such that <math>a_1 \, | \, a_2 \, | \, a_3 \, | \, a_4 \, | \, a_5 \, | \, a_6 \, | \, a_7 \, | \, 6468</math>, that is, <math>a_1</math> divides <math>a_2</math>, <math>a_2</math> divides <math>a_3</math>, <math>a_3</math> divides <math>a_4</math>, <math>a_4</math> divides <math>a_5</math>, <math>a_5</math> divides <math>a_6</math>, <math>a_6</math> divides <math>a_7</math>, and <math>a_7</math> divides <math>6468</math>.
  

Revision as of 07:37, 2 August 2024

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2010_Problems/Problem_2&oldid=224198"