今日学段:组合 + 概率(AMC 10/12 难度)
题目来源:MAA 美国数学竞赛官方真题(AIME I 2024,与 AMC 10/12 同属 MAA 高中竞赛体系;AoPS 维基实时源今日被 Cloudflare 拦截,故取自官方授权题库 GAIR-NLP/AIME-Preview,题面与官方一致)
【组合】网格路径的转向计数
难度: ⭐⭐⭐(高中竞赛难度:组合计数 / 星棒法)
题目来源: 2024 AIME I Problem 6
知识点: 网格路径 · 组合计数 · 星棒法(Stars and Bars)· 对称性
题目:
考虑在一个 $8\times 8$ 的方格纸上,从左下角沿网格线走到右上角、总长度为 $16$ 的路径。求其中恰好改变方向 4 次的路径数量(改变方向的含义如题图示例所示)。
说明: 每条最短路径都由 8 次向右($R$)和 8 次向上($U$)的移动组成,共 16 步。
解题过程
-
一条最短路径由 8 个 $R$ 和 8 个 $U$ 构成。若路径”恰好转向 4 次”,则其走向必然是交替的,例如 $RURUR$(先横后竖再横…共 5 段)或 $URURU$(先竖后横…共 5 段)。这两种情形对称,算一种再乘 2 即可。
- 以 $URURU$ 型为例:路径被分成 3 段竖走向($U$)和 2 段横走向($R$)。
- 把 8 个 $U$ 分成 3 个非空段,用星棒法:$\binom{8-1}{3-1}=\binom{7}{2}=21$ 种;
- 把 8 个 $R$ 分成 2 个非空段:$\binom{8-1}{2-1}=\binom{7}{1}=7$ 种。
-
该型路径数为 $21\times 7 = 147$。对称型 $RURUR$ 同样为 147。
- 总数 $= 2\times 147 = \boxed{294}$。
常见错误
- 忘记”每段必须非空”:若直接用 $\binom{8+3-1}{3-1}$ 会多算含零长度段的非法情形。
- 漏乘对称性:只算 $URURU$ 一种,得到 147 而非 294。
- 把”转向 4 次”误当成”段数 4”——实际 4 次转向对应 5 段。
知识背景
网格路径计数是组合数学经典问题。从 $(0,0)$ 到 $(m,n)$ 的最短路径数为 $\binom{m+n}{m}$。当引入”转向次数”约束时,本质是先把同一种走向的移动切分为若干非空段(星棒法),再乘上起始方向的对称情况。这类思想也用于统计单词排列、路径规划等。
【概率】彩票条件概率
难度: ⭐⭐⭐(高中竞赛难度:条件概率 / 组合计数)
题目来源: 2024 AIME I Problem 4
知识点: 条件概率 · 贝叶斯思想 · 组合计数 · 容斥
题目:
Jen 参加一个抽奖:她从集合 $S={1,2,3,\dots,10}$ 中选出 $4$ 个互不相同的数字。主办方再从 $S$ 中随机选出 $4$ 个数字。
- 若她选出的数字中至少有 2 个与主办方选中的数字相同,则她中奖;
- 若她选出的 $4$ 个数字全部与主办方选中数字相同,则她中大奖。
已知她中奖,求她中大奖的概率,表示为最简分数 $\frac{m}{n}$,并求 $m+n$。
解题过程
-
设事件 $A=$中大奖,事件 $B=$中奖。所求为条件概率 $P(A\mid B)=\dfrac{P(A)}{P(B)}$(因为中大奖必然中奖,故 $P(B\mid A)=1$)。
-
总抽法:$\binom{10}{4}=210$。
-
中大奖(4 个全中):只有 $1$ 种匹配方式,分子对应 $1$。
- 中奖(至少 2 个相同)按相同个数分类:
- 恰好 2 个相同:从 Jen 的 4 个数中选 2 个被抽中 $\binom{4}{2}$,主办方剩下 2 个数从其余 $10-4=6$ 个数中选 $\binom{6}{2}$,共 $\binom{4}{2}\binom{6}{2}=6\times 15=90$;
- 恰好 3 个相同:$\binom{4}{3}\binom{6}{1}=4\times 6=24$;
- 恰好 4 个相同:$1$ 种。
- 合计中奖数 $=90+24+1=115$。
- 条件概率 $P(A\mid B)=\dfrac{1}{115}$,故 $\frac{m}{n}=\frac{1}{115}$,$m+n=1+115=\boxed{116}$。
常见错误
- 误把”至少 2 个相同”的分母当成总抽法 210:条件概率的分母应是”中奖”情况数 115,而非 210。
- 分类时重复或遗漏:恰好 2/3/4 个相同三类要穷尽且不重叠。
- 混淆”Jen 选”与”主办方选”:两者都是从同一集合选 4 个,匹配数是组合交叉计数。
知识背景
条件概率 $P(A\mid B)=P(A\cap B)/P(B)$ 是概率论基石。当 $A\subset B$ 时退化为 $P(A)/P(B)$。本题用纯组合计数求各类匹配数,是 AMC/AIME 高频题型,也常见于真实抽奖、抽样检验场景。
评论