今日学段:组合 + 概率(AMC 10/12 难度)
题目来源:AMC 10 竞赛真题(2022 AMC 10A / 2021 AMC 10B,取自 AoPS Wiki 题库)
【组合】整数配对计数
难度: ⭐⭐⭐⭐(高中竞赛中档偏难,AMC 10A 第 14 题)
题目来源: 2022 AMC 10A Problem 14
知识点: 计数原理 · 构造性配对 · 阶乘计数
题目:
把整数 $1$ 到 $14$ 分成 $7$ 对,要求每一对中较大的数至少是较小数的 $2$ 倍。问共有多少种分法?
$\textbf{(A) }108\qquad\textbf{(B) }120\qquad\textbf{(C) }126\qquad\textbf{(D) }132\qquad\textbf{(E) }144$
解题过程
第一步:确定”大数”与”小数”的分界。
若某一对中较大数为 $x$、较小数为 $y$,需 $x \ge 2y$。注意到 $8,9,\dots,14$ 这 $7$ 个数中任意两个都不能配成一对(因为 $14 < 2 \times 8$),所以它们必须分属 $7$ 个不同对,且都是各自对中的较大数;相应地 $1,2,\dots,7$ 都是较小数。
第二步:找出强制配对。
$7$ 的搭档必须 $\ge 14$,因此 $7$ 只能与 $14$ 配对:只有 $1$ 种选择。
第三步:按从大到小依次给 $6,5$ 等分配搭档。
- $6$ 的搭档需 $\ge 12$,可选 ${12,13}$($14$ 已用):$2$ 种;
- $5$ 的搭档需 $\ge 10$,可选 ${10,11,12,13}$ 中未用的:$3$ 种;
也就是说,对 $5 \le y \le 7$,随着 $y$ 每减小 $1$,可选集合多出 $2$ 个元素而被占用只多 $1$ 个,可选数恰好递增 $1$,共 $1 \times 2 \times 3 = 3!$ 种。
第四步:剩余数字自由配对。
给 $5,6,7$ 分配完后,剩下 $8,9$ 及 $10\sim 13$ 中未用的共 $4$ 个大数,而 $1,2,3,4$ 的约束是搭档 $\ge 8$——剩余任何大数都满足。所以 $1,2,3,4$ 与剩余 $4$ 个大数可任意配对:$4! = 24$ 种。
第五步:合并计数。
\[3! \times 4! = 6 \times 24 = 144.\]答案:$\textbf{(E) }144$
推广:对 $1,\dots,2n$ 作同样要求,答案为 $\left\lfloor \frac{n}{2} \right\rfloor! \cdot \left\lceil \frac{n}{2} \right\rceil!$。
常见错误
- 没有发现 $8\sim 14$ 必须全为”大数”,直接暴力枚举配对导致重复或遗漏;
- 忘记 $7$ 只能配 $14$ 这一强制条件,多算了不合法方案;
- 按”从小数选大数”计数时未及时扣除已被占用的数,导致乘法原理用错。
知识背景
这类”带约束的完美匹配计数”是组合数学中二部图匹配问题的初等形式。解题关键是排序后贪心分析可选集合的大小:把约束最紧的元素(这里是 $7$)先安排,再依次放宽。当每一步的可选数只依赖于步骤序号时,总数就是这些可选数的乘积——这正是乘法原理的典型应用。类似思想在 Hall 婚配定理、错位排列等问题中都有体现,是 AMC/AIME 计数题的高频套路。
【概率】骰子先偶后奇的概率
难度: ⭐⭐⭐(高中竞赛中档,AMC 10B 第 18 题)
题目来源: 2021 AMC 10B Problem 18
知识点: 条件概率 · 对称性 · 排列视角
题目:
反复掷一枚公平的 $6$ 面骰子,直到出现奇数为止。求在第一个奇数出现之前,每个偶数($2,4,6$)都至少出现过一次的概率。
$\textbf{(A) }\dfrac{1}{120}\qquad\textbf{(B) }\dfrac{1}{32}\qquad\textbf{(C) }\dfrac{1}{20}\qquad\textbf{(D) }\dfrac{3}{20}\qquad\textbf{(E) }\dfrac{1}{6}$
解题过程
方法一:逐步条件概率(忽略重复)。
事件等价于:按”首次出现”的顺序看,$2,4,6$ 三个偶数都排在任何奇数之前。重复掷出已出现过的数不影响结果,可以忽略。
- 第一个”新”数字是偶数的概率:$\dfrac{3}{6}$(6 个数中 3 个偶数);
- 在此条件下,下一个与之前不同的”新”数字仍是偶数的概率:$\dfrac{2}{5}$(剩 5 个候选中 2 个偶数);
- 再下一个”新”数字是最后一个偶数的概率:$\dfrac{1}{4}$。
三个偶数集齐后,之后出现的新数字必是奇数,条件自动满足。故
\[P = \frac{3}{6} \cdot \frac{2}{5} \cdot \frac{1}{4} = \frac{1}{20}.\]方法二:对称性一步到位。
由对称性,$1\sim 6$ 中最先出现的 $3$ 个互不相同的数字,等可能地是 $\binom{6}{3} = 20$ 个三元组中的任何一个。目标事件即”最先出现的三个数恰为 ${2,4,6}$”,概率为
\[\frac{1}{\binom{6}{3}} = \frac{1}{20}.\]方法三:排列视角。
只看 $1,2,3,4,5,6$ 首次出现的先后顺序,它是 $6$ 个数的均匀随机排列。要求前三位恰为三个偶数:$\dfrac{3! \cdot 3!}{6!} = \dfrac{36}{720} = \dfrac{1}{20}$。
答案:$\textbf{(C) }\dfrac{1}{20}$
常见错误
- 试图对”掷了多少次、每个数重复几次”做无穷级数求和——虽然可行但极易算错;正确做法是意识到重复投掷可忽略;
- 误以为答案是 $\left(\frac{1}{2}\right)^3 = \frac{1}{8}$,忽略了三个偶数必须各不相同地先出现;
- 用排列视角时忘记乘偶数内部的 $3!$ 排法或奇数内部的 $3!$ 排法。
知识背景
本题是”首达顺序”(first-occurrence ordering)问题的经典例子:反复独立采样时,各元素首次出现的相对顺序构成一个均匀随机排列,与重复次数无关。这一事实让许多看似需要无穷级数的概率题瞬间化简,比如优惠券收集问题(Coupon Collector)的变体、竞赛中常见的”某些牌先于另一些牌被翻出”等问题。掌握”忽略无效试验 + 对称性”的思想,是处理几何分布叠加类概率题的利器。
评论