2004 AIME I 第 15 题

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

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

15.

对所有正整数 xx,定义 f(x)={1if x=1,x/10if x is divisible by 10,x+1otherwise,f(x) = \scriptsize\begin{cases} 1 & \text{if } x = 1, \\ x/10 & \text{if } x \text{ is divisible by } 10, \\ x + 1 & \text{otherwise,} \end{cases} 并按如下方式定义一个数列:x1=xx_1 = x,且对所有正整数 nnxn+1=f(xn)x_{n+1} = f(x_n)。令 d(x)d(x) 为使 xn=1x_n = 1 成立的最小 nn。(例如,d(100)=3d(100) = 3d(87)=7d(87) = 7。)设 mm 为满足 d(x)=20d(x) = 20 的正整数 xx 的个数。求 mm 的不同质因数之和。

For all positive integers x,x, let f(x)={1if x=1,x/10if x is divisible by 10,x+1otherwise,f(x) = \scriptsize\begin{cases} 1 & \text{if } x = 1, \\ x/10 & \text{if } x \text{ is divisible by } 10, \\ x + 1 & \text{otherwise,} \end{cases} and define a sequence as follows: x1=xx_1 = x and xn+1=f(xn)x_{n+1} = f(x_n) for all positive integers n.n. Let d(x)d(x) be the smallest nn such that xn=1.x_n = 1. (For example, d(100)=3d(100) = 3 and d(87)=7.d(87) = 7.) Let mm be the number of positive integers xx such that d(x)=20.d(x) = 20. Find the sum of the distinct prime factors of m.m.

答案:511
知识点:递推计数树状图逆推法
难度评级:3370
解答:

倒推:若 f(z)=zf(z') = z,则 z=10zz' = 10z(总是可以);还可能有 z=z1z' = z - 1,前提是 z1z - 1 不是 1010 的倍数且 z11z - 1 \ne 1,即 zz 不以 11 结尾且 z2z \ne 2。因此满足 d(x)=nd(x) = n 的整数构成一棵以 11 为根的树的第 nn 列:前几列为 {1}\{1\}{10}\{10\}{9,100}\{9, 100\}{8,90,99,1000}\{8, 90, 99, 1000\},并且除 22 和以 11 结尾的顶点以外,每个顶点都有两个子节点;那些例外只有子节点 10z10z

找出这些只有一个子节点的顶点。因为 231012 \to 3 \to \cdots \to 10 \to 1,顶点 22 位于第 1010 列。以 11 结尾的顶点可由一个以 00 结尾的顶点连续减 11 九次到达,所以这样的顶点位于树中那些 1010 的倍数之后 99 列。第 22 到第 1010 列完全翻倍(那之前没有只有一个子节点的顶点),所以第 jj 列有 2j22^{j-2} 个顶点,其中 1010 的倍数,也就是第 j1j - 1 列顶点的子节点 10z10z,有 2j32^{j-3} 个。因此对 12k1912 \le k \le 19,第 kk 列含有 2k122^{k-12} 个以 11 结尾的顶点(第 1111 列没有,因为第 22 列中的 1010 的倍数是 1010 本身,它的后代 11 被排除;这个排除正好就是 22 缺少的那个子节点)。

kk 列中一个只有一个子节点的顶点,会从第 2020 列原本可能的 2182^{18} 个顶点中去掉 219k2^{19-k} 个。因此 m=21829k=12192k12219k=21829827=29(2912)=29509. \begin{aligned} m &= 2^{18} - 2^{9} \\ &\quad {}- \sum_{k=12}^{19} 2^{k-12} \cdot 2^{19-k} \\ &= 2^{18} - 2^9 - 8 \cdot 2^7 \\ &= 2^9(2^9 - 1 - 2) \\ &= 2^9 \cdot 509. \end{aligned} 因为 509509 是质数,mm 的不同质因数之和为 2+509=5112 + 509 = 511

Work backwards: f(z)=zf(z') = z for z=10zz' = 10z (always) and for z=z1z' = z - 1 (provided z1z - 1 is not a multiple of 1010 and z11,z - 1 \ne 1, i.e. zz does not end in 11 and z2z \ne 2). So the integers with d(x)=nd(x) = n form column nn of a tree rooted at 1:1: the columns begin {1},\{1\}, {10},\{10\}, {9,100},\{9, 100\}, {8,90,99,1000},\{8, 90, 99, 1000\}, and every vertex has two children except 22 and the vertices ending in 1,1, which have only the child 10z.10z.

Locate those one-child vertices. Since 23101,2 \to 3 \to \cdots \to 10 \to 1, the vertex 22 sits in column 10.10. A vertex ending in 11 is reached by subtracting 11 nine times from a vertex ending in 0,0, so such vertices sit 99 columns after the multiples of 1010 in the tree. Columns 22 through 1010 double perfectly (no one-child vertices occur that early), so column jj has 2j22^{j-2} vertices, of which the multiples of 1010 — the children 10z10z of column j1j - 1 — number 2j3.2^{j-3}. Hence for 12k19,12 \le k \le 19, column kk contains 2k122^{k-12} vertices ending in 11 (column 1111 has none, because the multiple of 1010 in column 22 is 1010 itself, whose descendant 11 is excluded — that exclusion is exactly the missing child of 22).

A one-child vertex in column kk removes 219k2^{19-k} of the potential 2182^{18} vertices from column 20.20. Therefore m=21829k=12192k12219k=21829827=29(2912)=29509. \begin{aligned} m &= 2^{18} - 2^{9} \\ &\quad {}- \sum_{k=12}^{19} 2^{k-12} \cdot 2^{19-k} \\ &= 2^{18} - 2^9 - 8 \cdot 2^7 \\ &= 2^9(2^9 - 1 - 2) \\ &= 2^9 \cdot 509. \end{aligned} Since 509509 is prime, the sum of the distinct prime factors of mm is 2+509=511.2 + 509 = 511.

← 第 14 题#14
完整试卷

其他年份的第 15 题