今日学段:组合 + 数论(AMC 10/12 难度)
题目来源:AMC 10/12 竞赛真题(Po-Shen Loh 题库)
【组合】委员会分配计数
难度: ★★★★★(压轴 / AMC 10 第 22 题)
题目来源: 2024 AMC 10B Problem 22(AMC 10/12 竞赛真题 · Po-Shen Loh 题库)
知识点: 组合计数 · 勒让德公式 · 质因数分解
题目:
(16) 个人将被分成 (4) 个不加区分的 (4) 人委员会。每个委员会将有一名主席和一名秘书。所有不同的分配方式数可以写成 (3^r M),其中 (r) 和 (M) 是正整数,且 (M) 不能被 (3) 整除。求 (r)。
- (A) (5)
- (B) (6)
- (C) (7)
- (D) (8)
- (E) (9)
解题过程
第 1 步:先数”纯分组”数。 把 (16) 人排成一列有 (16!) 种排法;依次切成 (4) 段、每段 (4) 人。段内任意交换顺序是同一种分组,要除以 ((4!)^4);四个委员会本身不可区分,再除以 (4!)。于是分组数为
[ \frac{16!}{(4!)^4\,4!} ]
第 2 步:再数”赋职”数。 每个四人委员会内部选 (1) 名主席((4) 种),再从剩下 (3) 人中选 (1) 名秘书((3) 种),共 (4\cdot 3=12) 种;四个委员会相互独立,共 (12^4) 种。
第 3 步:写出总方式数。
[ N=\frac{16!}{(4!)^4\,4!}\cdot 12^4 ]
第 4 步:用勒让德公式数 (3) 的幂次。 对素数 (p),(v_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\cdots)
- 分子 (16!):(\left\lfloor\frac{16}{3}\right\rfloor+\left\lfloor\frac{16}{9}\right\rfloor=5+1=6) 个因子 (3);
- 分母 ((4!)^4\,4!):每个 (4!=24) 恰含一个 (3)((24=8\cdot3)),共 (4\cdot1+1=5) 个;
- 因子 (12^4):(12) 含一个 (3),共 (4) 个。
于是
[ v_3(N)=6-5+4=5 ]
即 (r=5)(其余部分 (M=N/3^5) 不被 (3) 整除)。
答案:(A) (5)
常见错误
- 忘记除以 (4!)(误把四个委员会当成可区分的),分母少了一个因子 (3),会算出 (r=6)。
- 用勒让德公式时漏掉 (\left\lfloor 16/9 \right\rfloor=1) 这一层,把 (v_3(16!)) 误算成 (5)。
知识背景
本题把组合计数与 p 进赋值缝在一起:先搭出带阶乘的计数公式,再只追问”某个质因数的指数”。勒让德公式 (v_p(n!)=\sum\lfloor n/p^k\rfloor) 是处理这类问题的标准工具,AMC 很喜欢用”标准分解中某质数的次数”来包装大数。
【组合】网格演化计数
难度: ★★★★★(压轴 / AMC 12 第 18 题)
题目来源: 2022 AMC 12B Problem 18(AMC 10/12 竞赛真题 · Po-Shen Loh 题库)
知识点: 过程模拟 · 分类讨论
题目:
一个 (5 \times 5) 网格中的每个格子要么被填充、要么为空,每个格子最多有八个相邻格子(相邻指共享一条边或一个角)。网格按如下规则变换:
- 有 (2) 或 (3) 个被填充邻居的被填充格子保持填充;
- 恰好有 (3) 个被填充邻居的空格子变为填充;
- 其余所有格子保持为空或变为空。
原题附有样例变换图。假设 (5\times5) 网格有一圈空格子组成的边界,中间包围着一个 (3\times3) 子网格。问有多少种初始构型会在一次变换后变成”只有中心一个格子被填充”的网格?(同一构型的旋转和翻折视为不同构型。)
- (A) (14)
- (B) (18)
- (C) (22)
- (D) (26)
- (E) (30)
解题过程
第 1 步:界定初始可填充范围。 外圈一圈初始全空,只有内层 (3\times3) 的格子可能一开始就被填充。
第 2 步:中心格的存活条件。 目标态是只有中心被填充:
- 若中心初始为空:它必须恰好有 (3) 个填充邻居才能被点亮;
- 若中心初始已填充:它需要 (2) 或 (3) 个填充邻居才能保持。
第 3 步:其余格子必须全部变成空。 最关键的约束来自外圈:外圈的”边中点”格子(例如最右列中间那格)恰好与 (3\times3) 某一整条外边的 (3) 个格子相邻,所以 (3\times3) 的任何一条外边上的三个格子不能同时被填充;同时每个被填充的格子自己也必须死亡(其填充邻居数不能落在 ({2,3}) 中)。注意所有有效构型都恰有 (3) 个填充格子。
第 4 步:情形一(中心初始为空)。 中心的 (8) 个邻居中恰有 (3) 个被填充。以中心为原点建立”环坐标”,(8) 个邻居为 ((\pm1,0),(0,\pm1),(\pm1,\pm1))。按正方形的对称性检查全部三元组并验证上述约束,只剩 (4) 种类型,代表元为
[ \begin{gathered} {(-1,-1),(-1,0),(1,1)},\quad {(-1,-1),(-1,1),(1,-1)},\ {(-1,-1),(-1,1),(1,0)},\quad {(-1,-1),(0,1),(1,0)}. \end{gathered} ]
它们的对称轨道大小分别为 (8,4,4,4),共 (8+4+4+4=20) 种构型。
第 5 步:情形二(中心初始已填充)。 同样的邻居检查后,只剩 (2) 种构型:另外两个填充格是一对相对的角格。此时中心恰有 (2) 个填充邻居而保持填充,两个角格各自只与中心相邻(填充邻居数为 (1))因而死亡。
第 6 步:合计。
[ 20+2=22 ]
答案:(C) (22)
常见错误
- 忽略”共享角也算相邻”,把 (8) 邻居当成 (4) 邻居处理,会漏掉或错判大量构型。
- 只数出 (4) 种”对称类型”就作答,忘记题目规定旋转和翻折视为不同构型,需要按轨道大小 (8,4,4,4) 还原计数。
知识背景
这是元胞自动机(与生命游戏同款规则)的一步逆向计数问题。正向规则很简单,逆向枚举则要善用对称群,把 (2^9) 种内层构型压缩成少数等价类,再逐一验证局部约束——这正是组合计数里”对称性约化”的标准打法。
评论