今日学段:数论 + 组合(AMC 10/12 难度)
题目来源:AMC 10 竞赛真题(通过 mathmastery 题库抓取)
【数论】GCD 与 LCM 的有序正整数对
难度: ⭐⭐⭐(高中竞赛 · 数论基础)
题目来源: AMC 10 · GCD and LCM
知识点: 最大公约数 · 最小公倍数 · 质因数分解 · 互质计数
题目:
满足条件的有序正整数对 $(a,b)$ 共有多少组,使得 $\gcd(a,b)=6$ 且 $\operatorname{lcm}(a,b)=540$?
- (A) $2$
- (B) $4$
- (C) $6$
- (D) $8$
- (E) $10$
解题过程
设 $a=6s,\ b=6t$,其中 $s,t$ 为正整数且 $\gcd(s,t)=1$。
由最小公倍数公式:
\[\operatorname{lcm}(a,b)=rac{ab}{\gcd(a,b)}=rac{36st}{6}=6st\]已知 $\operatorname{lcm}(a,b)=540$,故
\[6st=540 \quad\Rightarrow\quad st=90\]对 $90$ 做质因数分解:
\[90 = 2 imes 3^2 imes 5\]我们需要在 $st=90$ 的条件下,找出满足 $\gcd(s,t)=1$ 的无序对 $(s,t)$(之后再乘 $2$ 得到有序对)。
枚举 $90$ 的因数对(不妨设 $s\le t$):
| $(s,t)$ | $\gcd(s,t)$ | 是否互质 |
|---|---|---|
| $(1,90)$ | $1$ | ✓ |
| $(2,45)$ | $1$ | ✓ |
| $(3,30)$ | $3$ | ✗ |
| $(5,18)$ | $1$ | ✓ |
| $(6,15)$ | $3$ | ✗ |
| $(9,10)$ | $1$ | ✓ |
互质的无序对共有 $4$ 组:$(1,90),(2,45),(5,18),(9,10)$。
每一组无序对对应 $2$ 个有序对(交换 $s,t$),因此有序对总数为:
\[4 imes 2 = 8\]答案:(D) $8$
常见错误
- 忘记”有序对”需乘 $2$,只数出 $4$ 组无序对而误选 (B)。
- 误以为 $(3,30)$、$(6,15)$ 也互质——其实它们有公因子 $3$,必须剔除。
- 直接令 $a\cdot b=6 imes540$ 后乱枚举,没有先提取公因子 $6$,导致重复或遗漏。
知识背景
对于任意正整数 $a,b$,恒有 $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab$。当二者乘积已知后,可设 $a=gx,\ b=gy$(其中 $g=\gcd(a,b),\ \gcd(x,y)=1$),则 $\operatorname{lcm}(a,b)=gxy$。于是问题转化为”在 $xy=N$ 的约束下,统计互质因子的配对方式”。这是 AMC 数论中极经典的一类题,核心是质因数分解 + 互质条件。
【组合】圆排列中的相邻限制
难度: ⭐⭐⭐(高中竞赛 · 排列组合)
题目来源: AMC 10 · Circular Permutations
知识点: 圆排列 · 补集思想 · 捆绑法
题目:
$6$ 个人站成一个圆圈,其中指定的两个人不能相邻。共有多少种站法?
- (A) $48$
- (B) $60$
- (C) $72$
- (D) $72$
- (E) $96$
解题过程
总排列数(无限制):
$n$ 个人围成一圈,圆排列数为 $(n-1)!$。因此 $6$ 人无限制站法:
\[(6-1)! = 5! = 120\]违反条件的站法(两人相邻):
用捆绑法,把这两个必须相邻的人看作一个整体(一个”块”)。此时相当于 $5$ 个对象(块 + 其余 $4$ 人)围成一圈:
\[(5-1)! = 4! = 24\]块内部两人可以左右互换,有 $2$ 种排法。故相邻站法数为:
\[4! imes 2 = 24 imes 2 = 48\]满足条件的站法(补集):
\[120 - 48 = 72\]答案:(C) $72$
常见错误
- 用直线排列 $6!$ 而非圆排列 $5!$ 作为总数,导致后续全部算错。
- 忘记块内部两人的 $2$ 种内部排列,得到 $120-24=96$ 误选 (E)。
- 圆排列中”旋转视为相同”,但”翻转(镜像)是否相同”需注意:本题默认旋转等价、镜像不等价(一般圆排列标准定义),故总数为 $5!$ 而非 $5!/2$。
知识背景
圆排列与直线排列的关键区别在于旋转等价:固定一人位置后,其余 $n-1$ 人相对排列,故总数为 $(n-1)!$。处理”某些元素不能相邻”的约束时,补集 + 捆绑法是最常用套路:先算总数,再算”最坏情况”(指定元素相邻,捆绑成块)并扣除。这一思想在 AMC 10/12 的组合题中反复出现。
评论