题目

查看数据源：5c9308e3210b286d125ef4ce

一标记从坐标网格的原点 $\left( 0\text{,}0 \right)$ 出发连续移动六步，每步都沿平行于坐标轴方向且移动距离为 $1$ 。每步都等可能的沿四个方向之一且步与步之间相互独立。六步之后标记落在 $\left| y \right|\text{=}\left| x \right|$ 的图像上的概率为 $\frac{m}{n}$，其中 $m\text{,}n$ 为互质正整数。求 $m+n$

【难度】

【出处】

2014年第32届美国数学邀请赛Ⅰ（AIMEⅠ）

【标注】

题型
>
计数与概率
>
概率计算题
知识点
>
计数与概率
>
排列数与组合数

【答案】

391

【解析】

我们记四种移动方式为 $U,D,R,L$ 。可能的路径总数为 ${{4}^{6}}\text{=}4096$ 。最终落在直线 $y\text{=}x$ 上有四种可能：$x\text{,}y\text{=}\pm 1\text{;}x\text{,}y\text{=}\pm2\text{;}x\text{,}y\text{=}\pm 3\text{;}x\text{=}y\text{=}0$ 。我们下面只需分别计算出终点为 $\left(1\text{,}1 \right)\left( 2\text{,}2 \right)\left( 3\text{,}3 \right)$ 的路径总数，其 $4$ 倍再加上终点为 $\left(0\text{,}0 \right)$ 的即为全部可能路径数。
终点为 $\left(3\text{,}3 \right)$，路径为 $RRRUUU$ 的排列，共
终点为 $\left(2\text{,}2 \right)$，路径为 $RRRLUU$ 或 $UUUDRR$ 的排列，共 $2\left( \begin{matrix}
6 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}5 \\
2 \\
\end{matrix}\right)=120$ 种
终点为 $\left(1\text{,}1 \right)$，路径为 $RUUUDD$，$URRRLL$ 或 $UUDRRL$ 的排列，共 $\left( \begin{matrix}
6 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}5 \\
2 \\
\end{matrix} \right)+\left( \begin{matrix}6 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}5 \\
2 \\
\end{matrix} \right)+\left( \begin{matrix}6 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}5 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}4 \\
2 \\
\end{matrix} \right)\text{=}60+60+180\text{=}300$ 种
终点为 $\left( 0\text{,}0 \right)$，路径为 $RRRLLL$，$UUUDDD$，$RLUUDD$ 或 $RRLLUD$ 的排列，共 $\left( \begin{matrix}
6 \\
3 \\
\end{matrix} \right)+\left( \begin{matrix}6 \\
3 \\
\end{matrix} \right)+\left( \begin{matrix}6 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}5 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}4 \\
2 \\
\end{matrix} \right)+\left( \begin{matrix}6 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}5 \\
1 \\
\end{matrix} \right)\left( \begin{matrix}4 \\
2 \\
\end{matrix} \right)\text{=}20+20+180+180\text{=}400$ 种
满足条件的总路径数为 $4\times \left( 20+120+300 \right)+400\text{=}2160$ 种，所求概率为
$\frac{2160}{4096}\text{=}\frac{135}{256}$，所求值为 $135+256\text{=}391$

答案解析

我们记四种移动方式为 $U,D,R,L$ 。可能的路径总数为 ${{4}^{6}}\text{=}4096$ 。最终落在直线 $y\text{=}x$ 上有四种可能：$x\text{,}y\text{=}\pm 1\text{;}x\text{,}y\text{=}\pm2\text{;}x\text{,}y\text{=}\pm 3\text{;}x\text{=}y\text{=}0$ 。我们下面只需分别计算出终点为 $\left(1\text{,}1 \right)\left( 2\text{,}2 \right)\left( 3\text{,}3 \right)$ 的路径总数，其 $4$ 倍再加上终点为 $\left(0\text{,}0 \right)$ 的即为全部可能路径数。 终点为 $\left(3\text{,}3 \right)$，路径为 $RRRUUU$ 的排列，共 终点为 $\left(2\text{,}2 \right)$，路径为 $RRRLUU$ 或 $UUUDRR$ 的排列，共 $2\left( \begin{matrix} 6 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}5 \\ 2 \\ \end{matrix}\right)=120$ 种 终点为 $\left(1\text{,}1 \right)$，路径为 $RUUUDD$，$URRRLL$ 或 $UUDRRL$ 的排列，共 $\left( \begin{matrix} 6 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}5 \\ 2 \\ \end{matrix} \right)+\left( \begin{matrix}6 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}5 \\ 2 \\ \end{matrix} \right)+\left( \begin{matrix}6 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}5 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}4 \\ 2 \\ \end{matrix} \right)\text{=}60+60+180\text{=}300$ 种 终点为 $\left( 0\text{,}0 \right)$，路径为 $RRRLLL$，$UUUDDD$，$RLUUDD$ 或 $RRLLUD$ 的排列，共 $\left( \begin{matrix} 6 \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix}6 \\ 3 \\ \end{matrix} \right)+\left( \begin{matrix}6 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}5 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}4 \\ 2 \\ \end{matrix} \right)+\left( \begin{matrix}6 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}5 \\ 1 \\ \end{matrix} \right)\left( \begin{matrix}4 \\ 2 \\ \end{matrix} \right)\text{=}20+20+180+180\text{=}400$ 种 满足条件的总路径数为 $4\times \left( 20+120+300 \right)+400\text{=}2160$ 种，所求概率为 $\frac{2160}{4096}\text{=}\frac{135}{256}$，所求值为 $135+256\text{=}391$