今日年级:初二 + 初三
题目来源:NRICH Mathematics(英国剑桥大学数学竞赛题库)
【初二】数列中的整除性:Expanding Zeros
难度: ⭐⭐⭐(中等偏难)
题目来源: NRICH 2008 Problem 22 - Expanding Zeros
知识点: 整除性判断 · 数字求和规则 · 规律探究
题目:
观察下面这个无穷数列的规律:
\(27 = 3 \times 3 \times 3\) \(207 = 3 \times 3 \times 23\) \(2007 = 3 \times 3 \times 223\) \(20007 = 3 \times 3 \times 2223\) \(\vdots\)
以下哪个整数是 81 的倍数?
- a) $20\,000\,007$
- b) $2\,000\,000\,007$
- c) $200\,000\,000\,007$
- d) $20\,000\,000\,000\,007$
解题过程
第一步:理解数列结构
数列中的每一个数都可以写成 $2\underbrace{00\cdots0}_{n \text{ 个}}7$ 的形式, 而 $81 = 3^4$,所以我们要找 $3^4$ 的倍数。
第二步:分析因数结构
观察规律:
\[\underbrace{20\cdots07}_{n \text{ 个0}} = 3 \times 3 \times \underbrace{22\cdots23}_{n \text{ 个2, 末位3}}\]所以每个数都已经有因子 $3^2 = 9$。要使整个数是 $81 = 3^4$ 的倍数,还需要 $\underbrace{22\cdots23}$ 是 $9$ 的倍数。
第三步:判断 $\underbrace{22\cdots23}$ 何时是 9 的倍数
利用整除9的法则:各位数字之和是9的倍数。
设 $\underbrace{22\cdots23}$ 有 $k$ 个 “2” 和 1 个 “3”,则:
\[\text{数字之和} = 2k + 3\]要让 $2k+3$ 是9的倍数:
\[2k + 3 \equiv 0 \pmod{9} \implies 2k \equiv 6 \pmod{9} \implies k \equiv 3 \pmod{9}\]所以最小的 $k = 3$,即 $\underbrace{22\cdots23}$ 有 3个”2”(例如 $2223$)时是9的倍数,
下一个是 $k=12$,即 12个”2”($22222222222223$)。
第四步:对应到原数列
$\underbrace{22\cdots23}$ 中 “2” 的个数 = 原数 $\underbrace{20\cdots07}$ 中 “0” 的个数。
- a) $20000007$:6个0 → $k=6$,$2 \times 6+3=15$,不是9的倍数
- b) $2000000007$:8个0 → $k=8$,$2 \times 8+3=19$,不是9的倍数
- c) $200000000007$:10个0 → $k=10$,$2 \times 10+3=23$,不是9的倍数
- d) $20000000000007$:12个0 → $k=12$,$2 \times 12+3=27=3\times9$ ✅
答案:d) $20\,000\,000\,000\,007$
\[\boxed{d}\]常见错误
- 错误1:忘记原数已含因子 $9$,只考虑整个数能否被 $81$ 整除,而不是分解后的剩余因子。
- 错误2:数字求和时漏掉末位的 “3”,只数 “2” 的个数。
知识背景
整除性规律 是数论中最基础的工具之一。判断一个数能否被 $9$ 整除,只需看各位数字之和。本题巧妙地将”大数判断”转化为”数字位数计算”,是数学竞赛中常见的规律探究题型。类似的思路也出现在 AIME 和中国数学联赛中,训练同学们在无法直接计算时找到结构性规律。
【初三】Farey 分数序列
难度: ⭐⭐⭐⭐(较难)
题目来源: NRICH - Farey Sequences
知识点: 分数排序 · 数论性质 · 序列规律 · 欧拉 $\phi$ 函数
题目:
数学家 John Farey 研究了一类特殊的分数序列,称为 Farey 序列。
第三阶 Farey 序列 $F_3$ 如下:将所有分母不超过 3、介于 0 和 1 之间(含端点)的最简分数按升序排列:
\[F_3: \quad \frac{0}{1} \quad \frac{1}{3} \quad \frac{1}{2} \quad \frac{2}{3} \quad \frac{1}{1}\]类似地,$F_4$ 是分母不超过 4 的最简分数升序排列:
\[F_4: \quad \frac{0}{1} \quad \frac{1}{4} \quad \frac{1}{3} \quad \frac{1}{2} \quad \frac{2}{3} \quad \frac{3}{4} \quad \frac{1}{1}\]请完成以下探究:
- 写出 $F_5$。$F_5$ 中比 $F_4$ 多了哪些分数?它们出现在什么位置?
- $F_{11}$ 比 $F_{10}$ 多几个分数?$F_{12}$ 比 $F_{11}$ 多几个?
- 每个 Farey 序列都比前一个更长吗?如何证明?
- 能找到一个分数个数为偶数的 Farey 序列吗?(提示:$F_1, F_2, \ldots$ 都含奇数个分数,真的每个都这样吗?)
解题过程
第一步:写出 $F_5$
分母不超过 5 的最简分数,加入 $\frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}$:
\[F_5: \frac{0}{1}\ \frac{1}{5}\ \frac{1}{4}\ \frac{1}{3}\ \frac{2}{5}\ \frac{1}{2}\ \frac{3}{5}\ \frac{2}{3}\ \frac{3}{4}\ \frac{4}{5}\ \frac{1}{1}\]第二步:$F_n$ 的长度公式
$F_n$ 中分数的个数为:
\[|F_n| = 1 + \sum_{k=1}^{n} \phi(k)\]其中 $\phi(k)$ 是欧拉 phi 函数($\le k$ 中与 $k$ 互质的正整数个数)。
- $\phi(10) = 4$(与10互质的数:1,3,7,9),所以 $F_{11}$ 比 $F_{10}$ 多 4 个分数
- $\phi(11) = 10$(11是质数),所以 $F_{12}$ 比 $F_{11}$ 多 10 个分数
第三步:每个序列都比前一个长?
是的。因为每个正整数 $n \ge 2$ 都至少有 $\phi(n) \ge 1$(至少 1 与任意数互质),所以每个新序列都至少增加1个分数。
第四步:分数个数的奇偶性
| $ | F_n | = 1 + \sum_{k=1}^{n} \phi(k)$。 |
| 对所有 $n \ge 1$,$\sum_{k=1}^{n} \phi(k)$ 始终为偶数(因为 $\phi(k)$ 对 $k \ge 3$ 均为偶数,而 $\phi(1)=\phi(2)=1$,两者之和为偶数)。因此 $ | F_n | $ 始终为奇数。 |
常见错误
- 错误1:忘记 $\frac{0}{1}$ 和 $\frac{1}{1}$ 都要包含在序列中,导致个数少2。
- 错误2:把非最简分数(如 $\frac{2}{4}$)也计入,造成重复。
知识背景
Farey 序列由英国地质学家 John Farey 于1816年发现,数学家 Cauchy 给出了证明。它与黎曼猜想有深刻联系——Farey 序列的某个偏差量趋向于零等价于黎曼猜想成立!欧拉 $\phi$ 函数则是数论中描述”互质数量”的核心工具,在 RSA 加密算法中扮演关键角色。本题训练同学们将具体问题抽象为数学函数,是初三进入高中数学的重要过渡。
评论