已知虫子从一个等边三角形的一个顶点出发，每次虫子随机等可能地爬向除自己所在定点另外两个顶点中的一个．假设虫子爬行10次后恰回到出发点的概率为 $\frac{m}{n}$，其中 $m n$ 为互素的正整数，求 $m+n$．
【难度】
【出处】
2003年第21届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
683
【解析】
（1）若虫子从起点走了 $n$ 次之后回到起点，则在第 $n+1$ 次移动中，它走到起点的概率为 $0$，走到非起点的概率为 $1$．
（2）若虫子从起点走了 $n$ 次之后未回到起点，则在第 $n+1$ 次一佛那个中，它走到起点和非起点的概率均为 $\frac{1}{2}$．
设 ${{P}_{n}}$ 在 $n$ 次移动后，虫子恰回到起点的概率，则 ${{P}_{n+1}}=0\cdot{{P}_{n}}+\frac{1}{2}\left( 1-{{P}_{n}} \right)$，即 ${{P}_{n+1}}-\frac{1}{3}=\frac{1}{2}\left({{P}_{n}}-\frac{1}{3} \right)$．
由于 ${{P}_{0}}-\frac{1}{3}=1-\frac{1}{3}=\frac{2}{3}$，故 ${{P}_{n}}=\frac{1}{3}+\frac{2}{3}\cdot{{\left( -\frac{1}{2} \right)}^{n}}=\frac{{{2}^{n-1}}+{{\left( -1\right)}^{n}}}{3\cdot {{2}^{n-1}}}$．
特别地，${{P}_{10}}=\frac{171}{512}$，即 $m+n=683$．
（2）若虫子从起点走了 $n$ 次之后未回到起点，则在第 $n+1$ 次一佛那个中，它走到起点和非起点的概率均为 $\frac{1}{2}$．
设 ${{P}_{n}}$ 在 $n$ 次移动后，虫子恰回到起点的概率，则 ${{P}_{n+1}}=0\cdot{{P}_{n}}+\frac{1}{2}\left( 1-{{P}_{n}} \right)$，即 ${{P}_{n+1}}-\frac{1}{3}=\frac{1}{2}\left({{P}_{n}}-\frac{1}{3} \right)$．
由于 ${{P}_{0}}-\frac{1}{3}=1-\frac{1}{3}=\frac{2}{3}$，故 ${{P}_{n}}=\frac{1}{3}+\frac{2}{3}\cdot{{\left( -\frac{1}{2} \right)}^{n}}=\frac{{{2}^{n-1}}+{{\left( -1\right)}^{n}}}{3\cdot {{2}^{n-1}}}$．
特别地，${{P}_{10}}=\frac{171}{512}$，即 $m+n=683$．
答案
解析
备注
