数学题002-吉祥数

声明

出现的所有区间都默认与 $N^*$ 取交集。

题目

定义：若对于 $n \in N^*$，满足 $n$ 的各位数字相加之和为 $7$，则 $n$ 为吉祥数。

将所有的吉祥数由小到大排序，分别为 $a_1, a_2, \cdots$。

若 $a_n=2005$，求 $a_{5n}$。

解法

枚举位数

• 一位数只有一个吉祥数：$7$。

• 两位数中，如果第一位为 $x \in [1,7]$，则第二位必为 $7-x$，共 $7$ 种。

• 三位数中：

  • 当第一位是 $1$，第二位是 $x \in [0,6]$ 时，第三位是 $6-x$，共 $7$ 种。
  • 当第一位是 $2$，第二位是 $x \in [0,5]$ 时，第三位是 $5-x$，共 $6$ 种。
  • $\cdots$

不难发现，刚才的讨论过程中，既在对第一位讨论，同时也在对其余位的和讨论。

递推来源

定义：

• 后位和 $S(x)$ 为 $x$ 中除了第一位外，所有数位之和，即刚才的其余位的和。

• 位数 $D(x)$ 为 $x$ 的位数。

下面举两个例子：

• 对于一个三位吉祥数 $x$，它的第一位是 $1$（$1\_\ \_$），显然 $S(x)=6$。

  那么，如果把后两位拆分出来成为一个新的数 $x'$，此时 $S(x') \in [0,6]$，共 $7$ 种可能。

  所以，第一位是 $1$ 的三位吉祥数 有 $7$ 种可能。

• 对于一个四位吉祥数 $y$，它的第一位是 $2$（$2\_\ \_\ \_$），拆分后三位为 $y'$，则 $S(y') \in [0,5]$。

  • 当第二位是 $0$ 时，等价于 $2\_\ \_$ 的情况，有 $6$ 种。
  • 当第二位是 $1$ 时，等价于 $3\_\ \_$ 的情况，有 $5$ 种。
  • $\cdots$

  所以，$y$ 的可能方案数为所有 $D(a)=3$ 且 $S(a) \in [0,7-2]$的方案数。

综上，当吉祥数集合 $A$ 中所有元素 $x$ 以 $n$ 为第一位，$|A|$ 为 所有 $D(y)=D(x)-1$ 且 $S(y) \in [0,7-n]$ 的方案数。

列表

选用递推的思路，画出一张表格（横表头为 $S(x)$，纵表头为位数，内容为方案数）。

	$6$	$5$	$4$	$3$	$2$	$1$	$0$	总计
$1$	$0$	$0$	$0$	$0$	$0$	$0$	$1$	1
$2$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	8
$3$	$7$	$6$	$5$	$4$	$3$	$2$	$1$	$36$
$4$	$28$	$21$	$15$	$10$	$6$	$3$	$1$	$120$
$5$	$84$	$56$	$35$	$20$	$10$	$4$	$1$	$330$

表中一个数字等于它上方一行中在它右侧（含）的所有数字之和，符合上述性质。

显然，$2005$ 是所有的四位且以 $2$ 开头的最小吉祥数。

所以，$n=36+28+1=65$，$5n=325$。

查表得，$121 \lt 325 \lt 331$，所以 $a_{5n}$ 是五位数。

因为 $120+84+56+35+20=315$，$315+10=325$，所以 $S(a_{5n})=2$，$a_{5n}$ 以 $5$ 开头，且它是 $5$ 开头的五位数中最大的吉祥数（$325$ 占最后一个位置）。

所以，可以直接观察得 $a_{5n}=52000$。

也可以列出所有满足条件的吉祥数验证：

$$50002,50011,50020,50101,50110,50200,51001,51010,51100,52000$$

其中，最后一个数 $52000$ 即为答案。