← Reading List
🧮 奥数题

奥数每日两题 2026-04-10:委员会分配计数 / 网格演化计数

奥数题数学AMC10AMC12组合数论

今日学段:组合 + 数论(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) 种内层构型压缩成少数等价类,再逐一验证局部约束——这正是组合计数里”对称性约化”的标准打法。


评论