2019 AIME II Problems/Problem 12
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
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.