Difference between revisions of "2019 AIME II Problems/Problem 12"
(Created blank page) |
m |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
+ | ==Problem== | ||
+ | For <math>n \ge 1</math> call a finite sequence <math>(a_1, a_2 \ldots a_n)</math> of positive integers <i>progressive</i> if <math>a_i < a_{i+1}</math> and <math>a_i</math> divides <math>a_{i+1}</math> for all <math>1 \le i \le n-1</math>. Find the number of progressive sequences such that the sum of the terms in the sequence is equal to <math>360</math>. | ||
+ | ==Solution== | ||
+ | If the first term is <math>x</math>, then dividing through by <math>x</math>, we see that we can find the number of progressive sequences whose sum is <math>\frac{360}{x} - 1</math>, and whose first term is not 1. If <math>a(k)</math> denotes the number of progressive sequences whose sum is <math>k</math> and whose first term is not 1, then we can express the answer <math>N</math> as follows: | ||
+ | |||
+ | <cmath>\begin{align*}N &= a(359) + a(179) + a(119) + a(89) + a(71) + a(59) + a(44) + a(39) \\ | ||
+ | &+ a(35) + a(29) + a(23) + a(19) + a(17) + a(14) + a(11) + a(9) \\ | ||
+ | &+ a(8) + a(7) + a(5) + a(4) + a(3) + a(2) + a(1) + 1 | ||
+ | \end{align*}</cmath> | ||
+ | |||
+ | The <math>+1</math> at the end accounts for the sequence whose only term is 360. Fortunately, many of these numbers are prime; we have <math>a(p) = 1</math> for primes <math>p</math> as the only such sequence is "<math>p</math>" itself. Also, <math>a(1) = 0</math>. So we have | ||
+ | |||
+ | <cmath> N = 15 + a(119) + a(44) + a(39) + a(35) + a(14) + a(9) + a(8) + a(4) </cmath> | ||
+ | |||
+ | For small <math>k</math>, <math>a(k)</math> is easy to compute: <math>a(4) = 1</math>, <math>a(8) = 2</math>, <math>a(9) = 2</math>. For intermediate <math>k</math> (e.g. <math>k=21</math> below), <math>a(k)</math> can be computed recursively using previously-computed values of <math>a(\cdot)</math>, similar to dynamic programming. Then we have | ||
+ | <cmath>\begin{align*} | ||
+ | a(14) &= 1+a(6) = 1+2 = 3\\ | ||
+ | a(35) &= 1+a(6)+a(4) = 1 + 2 + 1 = 4 \\ | ||
+ | a(39) &= 2 + a(12) = 2+4 = 6 \\ | ||
+ | a(44) &= 2 + a(21) + a(10) = 2+4+2=8 \\ | ||
+ | a(119) &= 1 + a(16) + a(6) = 1 + 3 + 2 = 6 | ||
+ | \end{align*}</cmath> | ||
+ | Thus the answer is <math>N = 15+6+8+6+4+3+2+2+1 = \boxed{47}</math>. | ||
+ | |||
+ | -scrabbler94 | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://youtu.be/T-8-B-XgiiI | ||
+ | |||
+ | ~MathProblemSkills.com | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=9Zfi2AVq6ak ~ MathEx | ||
+ | |||
+ | ==See Also== | ||
+ | {{AIME box|year=2019|n=II|num-b=11|num-a=13}} | ||
+ | {{MAA Notice}} |
Latest revision as of 19:21, 7 January 2023
Problem
For call a finite sequence of positive integers progressive if and divides for all . Find the number of progressive sequences such that the sum of the terms in the sequence is equal to .
Solution
If the first term is , then dividing through by , we see that we can find the number of progressive sequences whose sum is , and whose first term is not 1. If denotes the number of progressive sequences whose sum is and whose first term is not 1, then we can express the answer as follows:
The at the end accounts for the sequence whose only term is 360. Fortunately, many of these numbers are prime; we have for primes as the only such sequence is "" itself. Also, . So we have
For small , is easy to compute: , , . For intermediate (e.g. below), can be computed recursively using previously-computed values of , similar to dynamic programming. Then we have Thus the answer is .
-scrabbler94
Video Solution
~MathProblemSkills.com
Video Solution
https://www.youtube.com/watch?v=9Zfi2AVq6ak ~ MathEx
See Also
2019 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.