今日学段:数论 + 组合(AMC 10/12 难度)
题目来源:AMC 12 竞赛真题(artofproblemsolving.com 真实题库)
【数论】除数列表里的下一个数
难度: ⭐⭐⭐⭐(高中竞赛 / AMC 12 第 19 题难度)
题目来源: 2018 AMC 12B Problem 19
知识点: 因数与倍数 · 最大公约数 · 质因数分解 · 不等式放缩
题目:
Mary 选了一个偶的 $4$ 位数 $n$。她把所有 $n$ 的因数按从小到大的顺序从左到右写出来:$1,2,\ldots,\dfrac{n}{2},n$。在某个时刻,Mary 把 $323$ 写成了 $n$ 的一个因数。请问紧挨在 $323$ 右边写下的那个因数的最小可能值是多少?
$\textbf{(A) } 324 \qquad \textbf{(B) } 330 \qquad \textbf{(C) } 340 \qquad \textbf{(D) } 361 \qquad \textbf{(E) } 646$
解题过程
设 $d$ 为紧挨在 $323$ 右边的下一个因数。
-
若 $\gcd(323,d)=1$,则因为 $323$ 与 $d$ 互素,它们的乘积仍是 $n$ 的因数,故 \(n\ge 323d > 323^2 > 100^2 = 10000,\) 这与 $n$ 是 $4$ 位数($\le 9999$)矛盾。
-
因此 $\gcd(323,d)>1$。注意到 $323 = 17\times 19$,所以 $d$ 必须能被 $17$ 或 $19$(或两者)整除。
- 要找比 $323$ 大的最小这样的 $d$:
- 若 $d$ 被 $17$ 整除,最小可能为 $17\times 20 = 340$;
- 若 $d$ 被 $19$ 整除,最小可能为 $19\times 18 = 342$;
- 两者都整除则至少为 $17\times 19 = 323$ 的倍数 $646$。
所以候选最小值为 $340$。
- 验证:取 $d=340=17\times 20$,则 $\operatorname{lcm}(323,340)=17\times 19\times 20 = 6460$,这是一个合法的偶 $4$ 位数,且 $323 \mid 6460$、$340 \mid 6460$,且 $323$ 与 $340$ 之间不存在 $6460$ 的其他因数。
因此答案为 $\boxed{\textbf{(C) } 340}$。
常见错误
- 误以为下一个因数就是 $323+1=324$: 没利用「相邻两个数的乘积若大于 $n$ 则不能同时整除 $n$」这一关键性质。
- 忽略 $n$ 是 $4$ 位数上限: 不用 $n<10000$ 的放缩,就无法排除互素情况。
- 忘记 $323=17\times 19$ 的分解: 这是整道题的突破口,分解错误则全盘皆错。
知识背景
本题是「因数成对出现」与「互素因数乘积下界」思想的经典应用。若 $a,b$ 都是 $n$ 的因数且互素,则 $ab\mid n$,所以 $ab\le n$。当已知 $n$ 有上界时,可用此放缩限制下一个因数的结构,常常只需检查「能被已知因数的质因子整除」的最小数。这类放缩在数论题中极常见。
【组合】圆桌错位就座
难度: ⭐⭐⭐⭐(高中竞赛 / AMC 12 第 22 题难度)
题目来源: 2015 AMC 12B Problem 22
知识点: 圆排列 · 容斥与递推 · 对称变换 · 错位排列
题目:
六把椅子均匀地摆在一个圆桌周围。一开始每把椅子上都坐着一个人。现在每个人都站起来,再坐到一把椅子上,要求:不能坐回原来的椅子,也不能坐到与自己原来椅子相邻的椅子,并且最终每把椅子仍恰好坐一个人。问共有多少种就座方式?
$\textbf{(A)}\; 14 \qquad\textbf{(B)}\; 16 \qquad\textbf{(C)}\; 18 \qquad\textbf{(D)}\; 20 \qquad\textbf{(E)}\; 24$
解题过程
巧妙办法:先做「整体平移」变换。把每个人落座后,令所有人统一逆时针平移 $3$ 个座位。经过这个对称变换:
- 原题中「不能坐原座、不能坐相邻座」$\iff$ 变换后「可以坐原座、也可以坐相邻座」。
- 于是问题转化为:六个人坐在圆周上,每人坐「自己原位或相邻位」,且每座恰一人,有多少种方式?
记 $F_n$ 为 $n$ 个人排成一行、每人坐自己原位或相邻位的方案数。对最左端的人:
- 若他不动,剩下 $n-1$ 人成行:$F_{n-1}$ 种;
- 若他右移到第 $2$ 位,则第 $2$ 个人必到最左位,剩下 $n-2$ 人成行:$F_{n-2}$ 种。
故递推 $F_n = F_{n-1}+F_{n-2}$,且 $F_1=1,\;F_2=2$,得 \(F_3=3,\;F_4=5,\;F_5=8,\;F_6=13.\)
回到圆周上的 $6$ 个人,固定某一个人 $P$:
- 若 $P$ 不动,其余 $5$ 人成行:$F_5=8$ 种;
- 若 $P$ 左移一位,则补到 $P$ 原位的人只能是 $P$ 右边那人,从而所有人被迫统一平移,$1$ 种;
- 若 $P$ 右移一位,对称地也是 $1$ 种。
所以总数为 $8+1+1 = \boxed{\textbf{(D) } 20}$。
常见错误
- 直接套用直线错位排列公式: 圆桌的相邻约束与直线错排不同,且「不坐相邻」比普通错排更严格。
- 忘记对称变换的三种情形: 固定一人时,他左移/右移各产生 $1$ 种全平移解,容易漏算。
- 把行模型 $F_6=13$ 直接当答案: 圆周比行多出了「首尾相连」的额外约束,需单独处理固定点。
知识背景
本题展示了竞赛组合中常用的两个技巧:对称变换简化约束(把「禁止相邻」翻转为「允许相邻」)与递推建模(类似斐波那契的线性递推)。圆周排列的处理关键是「固定一人、分情况」,把环拆成链。类似的「禁止相邻重排」问题在 AMC/AIME 中频繁出现。
评论