今日学段:数论 + 组合(AMC 10/12 难度)
题目来源:AMC 12A 竞赛真题(经 AI-MO 官方题库整理,题面链接指向 AoPS Wiki)
【{seg1}】{p1_title}
难度: ⭐⭐⭐(高中竞赛数论基础题,考查质因数分解与 LCM/GCD 的相互约束)
题目来源: 2022 AMC 12A Problem 4
知识点: 质因数分解 · 最小公倍数与最大公约数
题目:
设正整数 $n$ 与 $18$ 的最小公倍数为 $180$,且 $n$ 与 $45$ 的最大公约数为 $15$。求 $n$ 的各位数字之和。
解题过程
第一步:把所有数字写成质因数分解形式。
\[18 = 2^1 \cdot 3^2, \quad 180 = 2^2 \cdot 3^2 \cdot 5^1, \quad 45 = 3^2 \cdot 5^1, \quad 15 = 3^1 \cdot 5^1.\]设 $n = 2^a \cdot 3^b \cdot 5^c \cdot (\text{其他质因子})$。
第二步:用 LCM 条件 $\operatorname{lcm}(n,18)=180$ 约束各指数。
对每个质因子,LCM 取两数指数的最大值:
- 质因子 $2$:$\max(a,1)=2 \Rightarrow a=2$。
- 质因子 $3$:$\max(b,2)=2 \Rightarrow b\le 2$。
- 质因子 $5$:$\max(c,0)=1 \Rightarrow c=1$。
- $180$ 不含其他质因子,故 $n$ 也不能含其他质因子。
第三步:用 GCD 条件 $\gcd(n,45)=15$ 确定 $b$。
GCD 取两数指数的最小值:
- 质因子 $3$:$\min(b,2)=1 \Rightarrow b=1$。
- 质因子 $5$:$\min(c,1)=1$,与 $c=1$ 一致。
第四步:确定 $n$ 并求数字之和。
\[n = 2^2 \cdot 3^1 \cdot 5^1 = 4 \cdot 3 \cdot 5 = 60.\]各位数字之和为 $6 + 0 = \boxed{6}$。
常见错误
- 只用 LCM 条件而忽略 GCD,误以为 $b$ 可取 $0,1,2$ 而得出多个答案;实际上 GCD 把 $b$ 唯一锁定为 $1$。
- 把 LCM 的「取最大值」和 GCD 的「取最小值」记反,导致指数方向错误。
- 忘记检查「$180$ 不含其他质因子」这一隐含约束,误加入多余质因子。
知识背景
对任意两个正整数,若写成质因数分解 $x=\prod p_i^{e_i}$、$y=\prod p_i^{f_i}$,则 $\gcd$ 对每个质因子取指数最小值、$\operatorname{lcm}$ 取最大值,并满足恒等式 $\gcd(x,y)\cdot\operatorname{lcm}(x,y)=x\cdot y$。这类「已知 LCM/GCD 反推原数」的题目,核心技巧就是逐个质因子分别列出 $\max$ / $\min$ 约束,把一个整数问题拆成若干独立的指数不等式,是 AMC 数论部分的高频套路。
【{seg2}】{p2_title}
难度: ⭐⭐⭐⭐(高中竞赛压轴级组合题,需要「按元素独立计数」的转化思想)
题目来源: 2023 AMC 12A Problem 24
知识点: 子集链计数 · 独立计数原理 · 幂的取模
题目:
设 $K$ 为满足下列条件的序列 $A_1, A_2, \dots, A_n$ 的个数:$n$ 是不超过 $10$ 的正整数,每个 $A_i$ 都是 ${1,2,3,\dots,10}$ 的子集,且对 $2\le i\le n$ 都有 $A_{i-1}\subseteq A_i$。例如 ${},\ {5,7},\ {2,5,7},\ {2,5,7},\ {2,5,6,7,9}$ 就是一个这样的序列(此时 $n=5$)。求 $K$ 除以 $10$ 的余数。
解题过程
第一步:固定长度 $n$,按元素独立计数。
固定链长为 $n$。考虑集合 ${1,\dots,10}$ 中的某个元素 $x$。由于 $A_1\subseteq A_2\subseteq\cdots\subseteq A_n$,一旦 $x$ 进入某个 $A_i$,之后就一直存在。于是 $x$ 的「命运」完全由它第一次出现的位置决定:可以在第 $1,2,\dots,n$ 个集合中首次出现,也可以自始至终都不出现——共 $n+1$ 种选择。
第二步:$10$ 个元素相互独立。
每个元素各自有 $n+1$ 种选择,且互不影响,故长度恰为 $n$ 的链共有
\[(n+1)^{10}\]条。
第三步:对 $n=1$ 到 $10$ 求和。
\[K = \sum_{n=1}^{10} (n+1)^{10} = \sum_{k=2}^{11} k^{10}.\]第四步:逐项取个位(模 $10$)。
只需每个 $k^{10}$ 的个位:
| $k$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|
| $k^{10}\bmod 10$ | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 |
相加:$4+9+6+5+6+9+4+1+0+1 = 45$。
\[K \equiv 45 \equiv \boxed{5} \pmod{10}.\]常见错误
- 试图直接枚举所有链,陷入 $n$ 与集合的双重组合爆炸;关键是转成「每个元素独立选首次出现位置」。
- 漏掉「元素从不出现」这一种情况,把 $n+1$ 误算成 $n$。
- 计算 $k^{10}\bmod 10$ 时忘记利用个位数的循环周期,导致算错某一项。
知识背景
「链计数」是组合中的经典模型:一条 $A_1\subseteq\cdots\subseteq A_n$ 的子集链,等价于给每个元素分配一个「加入时刻」$\in{1,\dots,n,\text{never}}$。这种「把整体结构拆到每个元素上独立决策」的思想,与「多重集排列」「隔板法」同属组合计数的核心技巧。最后一步的幂取模则依赖个位数的循环节($2,3,7,8$ 周期为 $4$;$4,9$ 周期为 $2$;$0,1,5,6$ 恒定),是数论与组合结合的常见收尾。
评论