Difference between revisions of "2019 AIME II Problems/Problem 12"
Brendanb4321 (talk | contribs) m (→Problem) |
|||
| Line 22: | Line 22: | ||
a(119) &= 1 + a(16) + a(6) = 1 + 3 + 2 = 6 | a(119) &= 1 + a(16) + a(6) = 1 + 3 + 2 = 6 | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
| − | Thus the answer is <math>N = 15+6+8+6+4+3+2+2+1 = \boxed{ | + | Thus the answer is <math>N = 15+6+8+6+4+3+2+2+1 = \boxed{47}</math>. |
-scrabbler94 | -scrabbler94 | ||
Revision as of 09:44, 8 October 2019
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
![\[N = 15 + a(119) + a(44) + a(39) + a(35) + a(14) + a(9) + a(8) + a(4)\]](http://latex.artofproblemsolving.com/9/3/9/939d04b54ac6c6ce2171c8a055c8b5f671603e83.png)
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
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. 
