2019 AIME II 第 12 题

先试着解答 2019 AIME II 第 12 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2019 AIME II 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

12.

n1n \ge 1,若一个正整数有限序列 (a1,a2,,an)(a_1, a_2, \ldots, a_n) 满足 ai<ai+1a_i \lt a_{i+1},且 aia_i 整除 ai+1a_{i+1}1in11 \le i \le n - 1。),则称其为递进的。求所有项之和等于 360360 的递进序列的个数。

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.

答案:47
知识点:递推计数整除性
难度评级:3060
解答:

整除关系具有传递性,所以递进序列的每一项都是第一项的倍数。若一个和为 360360 的序列长度至少为 22、第一项为 dd,则 d360d \mid 360,把其余项都除以 dd,得到一个首项至少为 22、和为 360dd=360d1\frac{360 - d}{d} = \frac{360}{d} - 1 的递进序列。这个对应可逆。因此若 g(s)g(s) 表示和为 ss、首项至少为 22 的递进序列个数,答案为 1+d360,d<360g ⁣(360d1)1 + \sum_{d \mid 360,\, d \lt 360} g\!\left(\frac{360}{d} - 1\right),其中开头的 11 计数单项序列 (360)(360)

同样的化简给出递推式 且 g(1)=0g(1) = 0;特别地,当 ss 为质数时 g(s)=1g(s) = 1。从小到大计算: g(2)=g(3)=g(4)g(2) = g(3) = g(4) =g(5)=g(7)=1= g(5) = g(7) = 1g(6)=1+g(2)=2g(6) = 1 + g(2) = 2g(8)=1+g(3)=2g(8) = 1 + g(3) = 2g(9)=1+g(2)=2g(9) = 1 + g(2) = 2g(10)=1+g(4)=2g(10) = 1 + g(4) = 2g(12)=1+g(5)+g(3)+g(2)g(12) = 1 + g(5) + g(3) + g(2) =4= 4g(14)=1+g(6)=3g(14) = 1 + g(6) = 3g(16)=1+g(7)+g(3)=3g(16) = 1 + g(7) + g(3) = 3g(21)=1+g(6)+g(2)=4g(21) = 1 + g(6) + g(2) = 4g(35)=1+g(6)+g(4)=4g(35) = 1 + g(6) + g(4) = 4g(39)=1+g(12)+g(2)=6g(39) = 1 + g(12) + g(2) = 6g(44)=1+g(21)+g(10)g(44) = 1 + g(21) + g(10) +g(3)=8+ g(3) = 8g(119)=1+g(16)+g(6)=6g(119) = 1 + g(16) + g(6) = 6g(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}

2323 个满足 d<360d \lt 360 的因数给出的参数为 360d1=359\frac{360}{d} - 1 = 3591791791191198989717159594444393935352929232319191717141411119988775544332211,对应的 gg-值为 1,1,6,11, 1, 6, 11,1,8,61, 1, 8, 64,1,1,14, 1, 1, 11,3,1,21, 3, 1, 22,1,1,12, 1, 1, 11,1,01, 1, 0,和为 4646。加上单项序列,得到 46+1=4746 + 1 = 47

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.

← 第 11 题#11
完整试卷

其他年份的第 12 题