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"

(created solution page)
 
m (category)
 
(3 intermediate revisions by the same user not shown)
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>.
  
 
== Solution ==
 
== Solution ==
−
<math>\boxed{944}</math>.
+
Note that <math>6468=2^2\cdot3\cdot7^2\cdot11</math>. Each successive term in the sequence <math>a_1,a_2,\ldots,a_7</math> 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 <math>2</math>s, one <math>3</math>, two <math>7</math>s, and one <math>11</math> into seven boxes. We do not necessarily need to use all of the factors (for example, all of the terms could be <math>1</math>), so we can think of this exclusion as adding an eighth box to our problem. For each of the singular prime factors, there are <math>\tbinom81=8</math> ways to arrange them into the <math>8</math> boxes. Because there are two such factors (<math>3</math> and <math>11</math>), together they have <math>8^2</math> possibilities. For each squared prime factor, they have <math>\tbinom82=28</math> ways if they are not in the same box and <math>\tbinom81=8</math> ways if they are. Because there are two such factors (<math>2</math> and <math>7</math>), together they have <math>(28+8)^2=36^2</math> possibilities. Thus, the total number of arrangements is <math>36^2\cdot8^2=288^2=82,944</math>, so our answer is <math>\boxed{944}</math>.
  
 
== See Also ==
 
== See Also ==
−
*[[Mock AIME 1 2010 Problems]]
+
{{Mock AIME box|year=2010|n=1|num-b=1|num-a=3}}
−
*[[Mock AIME 1 2010 Problems/Problem 1|Preceded by Problem 1]]
+
[[Category:Intermediate Combinatorics Problems]]
−
*[[Mock AIME 1 2010 Problems/Problem 3|Followed by Problem 3]]
 

Latest revision as of 08:46, 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

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2010_Problems/Problem_2&oldid=224210"