2019 AIME II Problem 12

Attempt Problem 12 of the 2019 AIME II below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2019 AIME II solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

12.

For n1n \ge 1 call a finite sequence (a1,a2,,an)(a_1, a_2, \ldots, a_n) of positive integers progressive if ai<ai+1a_i \lt a_{i+1} and aia_i divides ai+1a_{i+1} for 1in1.1 \le i \le n - 1. Find the number of progressive sequences such that the sum of the terms in the sequence is equal to 360.360.

Answer: 47
Concepts:recursive countingdivisibility
Difficulty rating: 3060
Solution:

Divisibility is transitive, so every term of a progressive sequence is a multiple of the first term. If a sequence with sum 360360 has length at least 22 and first term d,d, then d360,d \mid 360, and dividing the remaining terms by dd yields a progressive sequence with first term at least 22 and sum 360dd=360d1;\frac{360 - d}{d} = \frac{360}{d} - 1; this correspondence is reversible. So if g(s)g(s) denotes the number of progressive sequences with sum ss and first term at least 2,2, the answer is 1+d360,d<360g ⁣(360d1),1 + \sum_{d \mid 360,\, d \lt 360} g\!\left(\frac{360}{d} - 1\right), the leading 11 counting the sequence (360).(360).

The same reduction gives the recursion g(s)=1+es2e<sg ⁣(se1)(s2), \begin{aligned} g(s) &= 1 + \sum_{\substack{e \mid s \\ 2 \le e \lt s}} g\!\left(\frac{s}{e} - 1\right) \\ &\qquad (s \ge 2), \end{aligned} with g(1)=0;g(1) = 0; in particular g(s)=1g(s) = 1 when ss is prime. Working upward: g(2)=g(3)=g(4)g(2) = g(3) = g(4) =g(5)=g(7)=1;= g(5) = g(7) = 1; g(6)=1+g(2)=2;g(6) = 1 + g(2) = 2; g(8)=1+g(3)=2;g(8) = 1 + g(3) = 2; g(9)=1+g(2)=2;g(9) = 1 + g(2) = 2; g(10)=1+g(4)=2;g(10) = 1 + g(4) = 2; g(12)=1+g(5)+g(3)+g(2)g(12) = 1 + g(5) + g(3) + g(2) =4;= 4; g(14)=1+g(6)=3;g(14) = 1 + g(6) = 3; g(16)=1+g(7)+g(3)=3;g(16) = 1 + g(7) + g(3) = 3; g(21)=1+g(6)+g(2)=4;g(21) = 1 + g(6) + g(2) = 4; g(35)=1+g(6)+g(4)=4;g(35) = 1 + g(6) + g(4) = 4; g(39)=1+g(12)+g(2)=6;g(39) = 1 + g(12) + g(2) = 6; g(44)=1+g(21)+g(10)g(44) = 1 + g(21) + g(10) +g(3)=8;+ g(3) = 8; g(119)=1+g(16)+g(6)=6.g(119) = 1 + g(16) + g(6) = 6.

The 2323 divisors d<360d \lt 360 give arguments 360d1=359,\frac{360}{d} - 1 = 359, 179,179, 119,119, 89,89, 71,71, 59,59, 44,44, 39,39, 35,35, 29,29, 23,23, 19,19, 17,17, 14,14, 11,11, 9,9, 8,8, 7,7, 5,5, 4,4, 3,3, 2,2, 1,1, whose gg-values are 1,1,6,1,1, 1, 6, 1, 1,1,8,6,1, 1, 8, 6, 4,1,1,1,4, 1, 1, 1, 1,3,1,2,1, 3, 1, 2, 2,1,1,1,2, 1, 1, 1, 1,1,0,1, 1, 0, summing to 46.46. Adding the single-term sequence gives 46+1=47.46 + 1 = 47.

← Problem 11#11
Full Exam

Problem 12 in Other Years