2019 AIME II Problem 12

Below is the professionally curated solution for Problem 12 of the 2019 AIME II, 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 of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:recursive countingdivisibility

Difficulty rating: 3060

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.

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),g(s) = 1 + \sum_{\substack{e \mid s \\ 2 \le e \lt s}} g\!\left(\frac{s}{e} - 1\right) \qquad (s \ge 2), 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(5)=g(7)=1;g(2) = g(3) = g(4) = 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)=4;g(12) = 1 + g(5) + g(3) + g(2) = 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(3)=8;g(44) = 1 + g(21) + g(10) + 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,8,6,4,1,1,1,1,3,1,2,2,1,1,1,1,1,0,1, 1, 6, 1, 1, 1, 8, 6, 4, 1, 1, 1, 1, 3, 1, 2, 2, 1, 1, 1, 1, 1, 0, summing to 46.46. Adding the single-term sequence gives 46+1=47.46 + 1 = 47.

← Problem 11Full ExamProblem 13

Problem 12 in Other Years