Question

一个棋子从 $xy$ 坐标网格中的点 $(0, 0)$ 出发，然后连续移动六次。每次移动都沿某条坐标轴平行方向移动 $1$ 个单位。每次移动都从四个可能方向中随机选择，并且彼此独立。棋子最终落在图像 $|y| = |x|$ 上的概率为 $\frac{m}{n}$ ，其中 $m$ 和 $n$ 是互质的正整数。求 $m + n$ 。

A token starts at the point $(0, 0)$ of an $xy$ -coordinate grid and then makes a sequence of six moves. Each move is $1$ unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability that the token ends at a point on the graph of $|y| = |x|$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

答案

答案：391

知识点：随机游走独立事件容斥原理

难度评级：2990

解答：

使用对角坐标 $u = x + y$ 和 $v = x - y$ 。四种移动都会使 $u$ 改变 $\pm 1$ ，也使 $v$ 改变 $\pm 1$ ，并且四种移动正好等可能地实现四种符号组合，所以 $u$ 和 $v$ 是相互独立的六步 $\pm 1$ 随机游走。棋子最终在 $|y| = |x|$ 上，恰好等价于 $y = \pm x$ ，也就是 $u = 0$ 或 $v = 0$ 。

$u = 0$ 和 $v = 0$ 各自都要求三次 $+1$ 和三次 $-1$ ，概率为 $\binom{6}{3}/2^6 = \frac{20}{64} = \frac{5}{16}$ 。由独立性和容斥原理，所求概率为 $\begin{aligned} &\frac{5}{16} + \frac{5}{16} - \left(\frac{5}{16}\right)^2 \\ &= \frac{160 - 25}{256} = \frac{135}{256}. \end{aligned}$

因此 $m + n = 135 + 256 = 391$ 。

Work in the diagonal coordinates $u = x + y$ and $v = x - y.$ Each of the four moves changes $u$ by $\pm 1$ and $v$ by $\pm 1,$ and the four moves realize all four sign combinations equally often — so $u$ and $v$ perform independent six-step $\pm 1$ walks. The token ends on $|y| = |x|$ exactly when $y = \pm x,$ that is, when $u = 0$ or $v = 0.$

Each of $u = 0$ and $v = 0$ requires three $+1$ s and three $-1$ s, with probability $\binom{6}{3}/2^6 = \frac{20}{64} = \frac{5}{16}.$ By independence and inclusion-exclusion, the probability is $\begin{aligned} &\frac{5}{16} + \frac{5}{16} - \left(\frac{5}{16}\right)^2 \\ &= \frac{160 - 25}{256} = \frac{135}{256}. \end{aligned}$

Thus $m + n = 135 + 256 = 391.$

2014 AIME I 第 11 题

答案：391

难度评级：2990

解答：

其他年份的第 11 题