11. 概率状态 · Mastering AMC 10/12

11.00%

状态

在本节中，你将能够 把一个可能永远玩下去的游戏变成几个方程：每个状态一个未知数，然后解出来。

Amelia 和 Blaine 轮流掷硬币，谁先掷出正面谁赢。这个游戏可能永远进行下去。那么，怎样才能把 Amelia 获胜的所有情形都加起来呢？

不用一个个加。你看：两人都没掷中之后，游戏又回到了和开始时一模一样的局面，又轮到 Amelia 掷了。每一个这样的局面就是一个状态。

给每个状态设一个未知数：从这个状态出发获胜的概率。沿着从这个状态出发的每一条箭头，写出它的方程。然后解这个方程组。一个永远不会结束的游戏，就变成了两行代数式。

注意：如果从规则的角度看两个局面没有区别，它们获胜的概率就相同。把它们合并成一个状态。

动手探索先玩，再学公式

试一试： 读一读这两个方程。为什么 Blaine 的方程里没有“Amelia 赢”那一项，只有一项含 a？
试一试： 按“下一步”。先解出的是哪个方程？又把它代入了哪里？
试一试： 看从每个状态出发的箭头。为什么它们的概率加起来总是 1？
试一试： 在“状态中的对称性”上打开“演示给我看”，再打开“合并对称状态”。为什么 4 个角上的格子可以变成一个状态？

认识概念

概念 11.0.1 · 状态

当我们想求从不同局面或不同轮次出发“获胜”的概率时，就用状态。解状态问题分三步：

给从每个局面出发获胜的概率设一个未知数。
对每个局面，用其他状态表示从它出发获胜的概率，写出一个方程。
解这个方程组。

概念 11.0.2 · 状态中的对称性

做状态问题时，一定要留意对称性：获胜概率相同的局面可以共用一个未知数。这样方程会简单得多。

注 11.0.3

在状态很多的问题里，你常常需要写一个状态递推方程：用一条规则把每个状态和它相邻的状态联系起来，例如 $p_n = \frac12 p_{n-1} + \frac12 p_{n+1}$ 。

看例题先预测，再揭晓

例 11.1

AMC 12

Tom、Dick 和 Harry 在玩一个游戏。三人同时开始，每人反复抛一枚均匀的硬币，直到抛出第一个正面为止，然后停下。三人抛硬币的次数都相同的概率是多少？

1
设想一轮：三人同时抛。三人都抛出反面、因而谁也没停下的概率是多少？

先预测一下：
你的预测

在 YouTube 上打开

例 11.2

AMC 10

青蛙 Frieda 在一个 $3 \times 3$ 的方格网上开始一连串跳跃，每跳一次移动一格，每次跳跃的方向从上、下、左、右中随机选择。她不沿对角线跳。如果某次跳跃的方向会让 Frieda 跳出方格网，她就会“绕回来”，跳到对边去。例如，如果 Frieda 从中心格出发，向“上”跳两次，第一次会落在最上面一行的中间格，第二次则会让她跳到对边，落在最下面一行的中间格。假设 Frieda 从中心格出发，至多随机跳四次，如果落在角上的格子就停止跳跃。她在这四次跳跃中的某一次到达角上格子的概率是多少？

同一组里的每个状态，去往每一组的概率都相同，所以可以放心合并。

走 0 步后，处于角的概率：

0

每一步后处于各状态的概率
n	中心	边	角	总和
0	1	0	0	1

1
按对称性给这 9 个格子分组。一共有几类不同的格子？

先预测一下：
你的预测

在 YouTube 上打开

竞赛角真实竞赛题

习题 11.3.1

AMC 10

Amelia 有一枚硬币，抛出正面的概率是 $\frac13$ ；Blaine 有一枚硬币，抛出正面的概率是 $\frac25$ 。Amelia 和 Blaine 轮流抛各自的硬币，直到有人抛出正面为止；先抛出正面的人获胜。所有抛掷相互独立。Amelia 先抛。Amelia 获胜的概率是 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质的正整数。 $q - p$ 是多少？

习题 11.3.2

AMC 10

Debra 反复抛一枚均匀的硬币，并记录她总共看到了多少次正面和多少次反面，直到连续抛出两次正面或连续抛出两次反面为止，这时她停止抛掷。她以连续两次正面结束、但在看到第二次正面之前先看到了第二次反面的概率是多少？

习题 11.3.3

AMC 10

一只青蛙坐在点 $(1, 2)$ 处，开始一连串跳跃，每次跳跃都平行于某条坐标轴，长度为 $1$ ，每次跳跃的方向（上、下、右或左）独立随机地选择。当青蛙到达以 $(0, 0)$ 、 $(0, 4)$ 、 $(4, 4)$ 和 $(4, 0)$ 为顶点的正方形的某条边时，跳跃结束。跳跃在正方形的一条竖直边上结束的概率是多少？

习题 11.3.6

AMC 12挑战

一个小池塘里有一排 11 片荷叶，编号为 $0$ 到 $10$ 。一只青蛙坐在 $1$ 号荷叶上。当青蛙在 $N$ 号荷叶上（ $0 < N < 10$ ）时，它以 $\frac{N}{10}$ 的概率跳到 $N - 1$ 号荷叶，以 $1 - \frac{N}{10}$ 的概率跳到 $N + 1$ 号荷叶。每次跳跃都与之前的跳跃相互独立。如果青蛙到达 $0$ 号荷叶，它就会被一条耐心等候的蛇吃掉。如果青蛙到达 $10$ 号荷叶，它就会离开池塘，再也不回来。青蛙没有被蛇吃掉、成功逃脱的概率是多少？

过关检测（第 11.0 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

11.10%

状态与递推

在本节中，你将能够 用一张逐行填写的表格，求出恰好走 n 步后处于每个状态的概率。

一只蟋蟀在 4 片叶子之间跳，每次都跳到另一片叶子上。跳 4 次之后，它回到出发那片叶子的概率是多少？

有些问题问的是走了固定步数之后的情况，而不是“最后谁会赢”。这时就列一张表格：每一步占一行，每个状态占一列。每一行都由它上面那一行算出来。

注意：每一行的概率加起来都等于 1。如果不等于 1，说明你在某处漏掉了一条路径。

动手探索先玩，再学公式

叶子数4

跳了 0 次后：回到 A 的概率 =

1

每跳一次后，在每片叶子上的概率
跳数	A★	其他每片	所有叶子（总和 = 1）
0	1	0

每根条按叶子的颜色分段。每根条都是满的：概率之和总是 1。

试一试： 跳 4 次。表格的每一行加起来还是 1 吗？
试一试： 盯住叶子 A。为什么跳一次后它的概率总是（1 − 它上一次的概率）÷ 3？
试一试： 改成 5 片叶子。这条规则里的 3 要换成哪个数？

认识概念

概念 11.1.1 · 状态表

对于状态递推，一个好办法往往是直接列一张表，写出每个时刻处于每个位置的概率。记住：每一步的概率总和必须始终为 $1$ 。

注 11.1.2

递推方程与状态结合起来，很适合解决这样的问题：“走 10 步之后，位于点 $A$ 的概率是多少？”

“顶→底”的意思是：现在在底面，刚从顶面走下来。

走 1 步后，处于底→顶 / 顶→顶的概率：

\tfrac{1}{3}

每一步后处于各状态的概率
n	底→顶	顶→顶	顶→底	底→底	总和
1	1/3	0	0	2/3	1

正方体上的蚂蚁（例 11.5）：表格的每一行都由上一行算出。

注 11.1.3

即使不涉及概率，同样的表格技巧也管用。这时在表格的每一格里填方法数。

每一格记录的是停在该状态的路径条数。

走 1 步后，处于底→顶 / 顶→顶的方法数：

1

每一步后处于各状态的方法数
n	底→顶	顶→顶	顶→底	底→底	总和
1	1	0	0	2	3

还是蚂蚁的表格，这次数的是路径条数而不是概率。每一行的总和都翻一倍。

看例题先预测，再揭晓

例 11.3

AMC

一只蟋蟀在 4 片叶子之间随机跳跃，每一次都等可能地跳到另外 3 片叶子中的一片上。跳 4 次之后，蟋蟀回到出发时那片叶子的概率是多少？

跳了 0 次后：回到 A 的概率 =

1

每跳一次后，在每片叶子上的概率
跳数	A★	其他每片	所有叶子（总和 = 1）
0	1	0

每根条按叶子的颜色分段。每根条都是满的：概率之和总是 1。

1
把出发的叶子叫作 $A$ ，设 $p_n$ 为跳 $n$ 次后蟋蟀在 $A$ 上的概率。 $p_0 = 1$ 。 $p_1$ 是多少？

先预测一下：
你的预测

在 YouTube 上打开

例 11.4

AMC 10

Raashan、Sylvia 和 Ted 玩下面这个游戏。每人开始时各有 $\$1$ 。每 15 秒响一次铃，铃响时，当时手里有钱的每位玩家同时、独立且随机地从另外两位玩家中选一位，给那位玩家 $\$1$ 。铃响 2019 次之后，每位玩家都恰有 $\$1$ 的概率是多少？（例如，Raashan 和 Ted 可能都决定把 $\$1$ 给 Sylvia，而 Sylvia 可能决定把她的那一美元给 Ted，这时 Raashan 有 $\$0$ ，Sylvia 有 $\$2$ ，Ted 有 $\$1$ ，第一轮就此结束。在第二轮中，Raashan 没有钱可给，但 Sylvia 和 Ted 可能互相把各自的 $\$1$ 给对方，那么第二轮结束时各人的钱数和之前一样。）

同一组里的每个状态，去往每一组的概率都相同，所以可以放心合并。

走 0 步后，处于 1, 1, 1 的概率：

1

每一步后处于各状态的概率
n	1, 1, 1	2, 1, 0（任意顺序）	总和
0	1	0	1

1
总共有 $\$3$ 。不考虑玩家的顺序，一共可能有几种钱数分布？

先预测一下：
你的预测

在 YouTube 上打开

例 11.5

AIME

一只蚂蚁在正方体上走一连串的步，每一步是沿正方体的一条棱从一个顶点走到相邻的顶点。开始时蚂蚁在正方体底面的一个顶点上，第一步从三个相邻顶点中选一个走过去。第一步之后的每一步，蚂蚁都不返回它上一步所在的顶点，而是从另外两个相邻顶点中选一个走过去。所有选择都是随机的，每种可能的走法等可能。恰好走 8 步后蚂蚁位于正方体顶面某个顶点上的概率是 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

1
具体在哪个顶点并不重要：重要的只是蚂蚁在哪个面上，以及它是从哪里来的。第一步之后，共有 4 种不同的状态。它们是什么？

竞赛角真实竞赛题

习题 11.3.4

AIME

池塘里有一排荷叶，编号为 $1, 2, 3, \ldots$ 。一只青蛙从 $1$ 号荷叶出发，进行一连串跳跃。从任意 $k$ 号荷叶，青蛙跳到 $k + 1$ 号或 $k + 2$ 号荷叶，各以 $\frac12$ 的概率随机选择，且与其他跳跃相互独立。青蛙到过 $7$ 号荷叶的概率是 $\frac{p}{q}$ ，其中 $p$ 和 $q$ 是互质的正整数。求 $p + q$ 。

习题 11.3.5

AMC 10/12

一只青蛙按照以下规则在数轴上跳：

它从 $0$ 出发。
如果它在 $0$ ，那么它以 $\frac12$ 的概率移到 $1$ ，以 $\frac12$ 的概率消失。
对于 $n = 1, 2, 3$ ，如果它在 $n$ ，那么它以 $\frac14$ 的概率移到 $n + 1$ ，以 $\frac14$ 的概率移到 $n - 1$ ，以 $\frac12$ 的概率消失。

青蛙到达 $4$ 的概率是多少？

过关检测（第 11.1 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

11.20%

期望值状态

在本节中，你将能够 用状态求期望步数：方程和之前一样，只是要为你即将走的这一步加上 1。

两名实力相当的网球选手一直比下去，直到有人连赢三局。平均要打多少局？

期望值状态和概率状态的用法完全一样。每个状态设一个未知数：从这里出发还要走的期望步数。唯一的变化是：每个方程都要 +1，代表你即将走的这一步。

终点状态的值是 $0$ ：已经不需要再走了。

动手探索先玩，再学公式

每个状态一个方程（还需的期望步数）

每个状态的方程：沿着从它出发的每一条箭头写。

$a = 1 + \tfrac{1}{2}\,b_A + \tfrac{1}{2}\,b_B$
$b_A = 1 + \tfrac{1}{2}\,c_A + \tfrac{1}{2}\,b_B$
$b_B = 1 + \tfrac{1}{2}\,c_B + \tfrac{1}{2}\,b_A$
$c_A = 1 + \tfrac{1}{2}\,b_B$
$c_B = 1 + \tfrac{1}{2}\,b_A$

从“开始”出发的期望步数 = (请按“下一步”)

试一试： 为什么每个方程都以 1 + 开头？
试一试： 打开“合并对称状态”。为什么“A 连胜 1”和“B 连胜 1”其实是同一个状态？
试一试： 合并和不合并时各按一次“全部解出”。得到的期望局数一样吗？

认识概念

概念 11.2.1 · 期望值状态

期望值状态的用法和概率状态几乎完全一样。唯一的区别：每个方程都要加 1。例如

\text{从 } A \text{ 出发的期望步数} = \text{从 } B \text{ 出发的期望步数} + 1.

之所以加 $1$ ，是因为从 $A$ 走到 $B$ 要花 $1$ 步。

看例题先预测，再揭晓

例 11.6

SMT

假设两名实力相当的网球选手相互比赛，直到其中一人连赢三局为止。各局结果相互独立，每局两人获胜的概率相等。他们比赛局数的期望值是多少？

1
关键思路是两名选手之间的对称性。这场比赛一共有几种可能的状态？

先预测一下：
你的预测

竞赛角真实竞赛题

习题 11.3.8（补充题）

AIME挑战

青蛙 Freddy 在坐标平面上跳来跳去，寻找一条河，这条河位于水平直线 $y = 24$ 上。在水平直线 $y = 0$ 处有一道篱笆。每次跳跃时，Freddy 随机选择一个平行于某条坐标轴的方向，朝这个方向移动一个单位。当他位于 $y = 0$ 的某点时，他等可能地从三个方向中选一个：要么平行于篱笆跳，要么跳离篱笆；但他绝不会选择会让他越过篱笆、到达 $y < 0$ 的方向。Freddy 从点 $(0, 21)$ 开始寻找，一旦到达河上的某点就停下。求 Freddy 到达河所需跳跃次数的期望值。

过关检测（第 11.2 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。

11.3

练习题

在本节中，你将能够 在一道更难的竞赛题上运用状态和对称性。

一个粒子在正方形内部随机游走，直到碰到边界。可能的位置有 9 个，但对称性把它们缩减成 3 个状态。

想在一页上看到本章的所有题目？打开习题集。

竞赛角真实竞赛题

习题 11.3.7（补充题）

AMC 12挑战

在笛卡儿坐标平面上画一个正方形，顶点为 $(2, 2)$ 、 $(-2, 2)$ 、 $(-2, -2)$ 、 $(2, -2)$ 。一个粒子从 $(0, 0)$ 出发。每一秒，它等可能地移到离当前位置最近的八个格点（坐标都是整数的点）之一，且与之前的移动相互独立。换句话说，粒子从 $(x, y)$ 移到 $(x, y + 1)$ 、 $(x + 1, y + 1)$ 、 $(x + 1, y)$ 、 $(x + 1, y - 1)$ 、 $(x, y - 1)$ 、 $(x - 1, y - 1)$ 、 $(x - 1, y)$ 或 $(x - 1, y + 1)$ 中每一个的概率都是 $1/8$ 。粒子最终会第一次碰到正方形，碰到的位置要么是正方形的 $4$ 个角之一，要么是正方形各边内部的 $12$ 个格点之一。它碰到角而不是碰到边的内部格点的概率是 $m/n$ ，其中 $m$ 和 $n$ 是互质的正整数。 $m + n$ 是多少？