今日学段:数论 + 组合(AMC 10/12 难度)
题目来源:AMC 10 / AMC 12 美国数学竞赛真题(来源站点 wiki.randommath.com,题目版权归 MAA 美国数学协会所有)
【数论】阶乘整除判定:最小的 n 使 n! 是 2024 的倍数
难度: ⭐⭐⭐(高中竞赛 · 初等数论基础)
题目来源: 2024 AMC 10A Problem 5
知识点: 阶乘的质因数分解 · 勒让德公式(Legendre’s formula)· 整除条件
题目:
求最小的正整数 $n$,使得 $n!$ 是 $2024$ 的倍数?
- (A) $11$
- (B) $21$
- (C) $22$
- (D) $23$
- (E) $253$
解题过程
要判定 $n!$ 是否为 $2024$ 的倍数,只需看 $2024$ 的质因数分解:
\[2024 = 8 \times 253 = 2^3 \times 11 \times 23\]要使 $n!$ 同时含有因子 $2^3$、$11$、$23$,需要 $n!$ 中这三个质数的指数都不小于它们在 $2024$ 中的指数。
- 质因子 $23$: $n!$ 中包含因子 $23$ 当且仅当 $n \ge 23$(因为 $23$ 是质数,只有 $n \ge 23$ 时乘积里才会出现一个 $23$)。
- 质因子 $11$: 只要 $n \ge 11$ 即可,显然被 $n \ge 23$ 覆盖。
- 质因子 $2$(需要至少 $3$ 个): 勒让德公式给出 $v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\dots$,当 $n=23$ 时 $v_2(23!)=11+5+2+1=19 \gg 3$,绰绰有余。
因此最小满足条件的 $n$ 由”包含因子 $23$”这一最严格条件决定,即
\[n_{\min} = 23\]故答案为 (D) $23$。
常见错误
- 误以为 $2024 = 8 \times 253$ 里 $253 = 11 \times 23$ 不是质数,于是对 $253$ 再分解不到位,漏掉 $23$ 这个较大质因子,从而错误选 $11$ 或 $22$。
- 用”试算”去逐个检验 $n=11,21,22$ 是否被 $2024$ 整除,却没意识到 $n!$ 里若出现 $23$ 才算数,而 $23$ 是关键瓶颈。
- 忘记检查 $2$ 的指数(其实这里不是瓶颈),但养成”逐质因子核对指数”的习惯更重要。
知识背景
判断 $n!$ 能否被某个整数整除,标准方法是先把该整数做质因数分解,再对每一质因子 $p$ 用勒让德公式 $v_p(n!)=\sum_{k\ge1}\lfloor n/p^k\rfloor$ 计算 $n!$ 中 $p$ 的指数,要求它不小于目标整数中 $p$ 的指数。本题的”陷阱”在于 $2024$ 含有一个较大的质数 $23$,它比 $2$ 和 $11$ 都更严格地限制了 $n$ 的下界——这类”被最大质因子卡住”的直觉在竞赛中非常常见。
【组合】网格牙签闭环:Slitherlink 型路径计数
难度: ⭐⭐⭐⭐(高中竞赛 · 组合计数与分类讨论)
题目来源: 2024 AMC 12A Problem 22
知识点: 组合计数 · 分类讨论 · 连通分量 · 独立选择乘法原理
题目:
下图是一个 $8$ 格宽、$3$ 格高的点阵网格(由 $1’‘\times 1’’$ 的小方格组成)。Carl 在一些小方格的边上放置 $1$ 英寸长的牙签,以构成一个不自交的闭合回路。格子里标注的数字表示该方格有多少条边要被牙签覆盖;若某格没有数字,则该格边上可任意放置牙签(数量不限)。问 Carl 有多少种不同的放置牙签的方案?
- (A) $130$
- (B) $144$
- (C) $146$
- (D) $162$
- (E) $196$
解题过程
闭环要么完全绕在上半部分(围着第一行 $8$ 个格子形成一个 $8\times1$ 的矩形),要么完全绕在下半部分(围着第三行形成另一个 $8\times1$ 矩形)——这给出 $2$ 种方案。
其余情况,闭环必须穿过中间一行。一旦它进入中间行,按照规则它会在中间行两侧都笔直延伸,从而把网格分成左右两个连通部分;而闭环的两端必须进入同一个连通部分。于是闭环必须穿过最左两列之一与最右两列之一,共产生 $4$ 种”端部情形”。
在每种端部情形下,闭环的两端要连接起来:一端从上方跨过、一端从下方跨过,中间隔着若干个中间行的格子(标记为”$1$”)。设中间有 $n$ 个这样的格子,对每一个 $1$,回路可以覆盖它的上边或下边——两种选择相互独立,故有 $2^n$ 种连接方式。
四种端部情形分别给出:
- $1$ 种情形:$n=6$;
- $2$ 种情形:$n=5$;
- $1$ 种情形:$n=4$。
总方案数为
\[2^6 + 2\cdot 2^5 + 2^4 + 2 = 64 + 64 + 16 + 2 = 146\]故答案是 (C) $146$。
(注:这类在网格边上围出单条不自交回路的玩法,正是源自 1990 年代日本的经典逻辑谜题 Slitherlink(数回)。)
常见错误
- 只想到上下两个矩形($2$ 种),漏掉”穿过中间行且两端在同一侧连通部分”的大量情形,从而误选偏小答案。
- 在统计 $2^n$ 时把 $n$(中间行被穿过的格子数)数错,或没意识到”每个 $1$ 上下二选一”是相互独立的乘法关系。
- 把”4 种端部情形”各自对应的 $n$ 值分配错(应为 6、5、5、4),导致加总结果偏离 $146$。
知识背景
本题是组合计数里的”分类讨论 + 乘法原理”典型题。核心思路是:先按回路的”宏观形态”分成不重不漏的若干类(不穿中行 / 穿中行),再在每类内部用独立选择相乘、同类情形相加来计数。把局部的小选择(每个中间格选上边或下边)独立化、再用 $2^n$ 计数,是处理此类”二选一独立决策”结构的常用技巧。它背后的模型——Slitherlink——也是训练逻辑推理与计数直觉的好素材。
评论