HMMT 二月 2006 · 冲刺赛 · 第 17 题

HMMT February 2006 — Guts Round — Problem 17

[8] Begining at a vertex, an ant is crawls between the vertices of a regular octahedron. After reaching a vertex, it randomly picks a neighboring vertex (sharing an edge) and walks to that vertex along the adjoining edge (with all possibilities equally likely.) What is the probability that after walking along 2006 edges, the ant returns to the vertex where it began?

解析

Begining at a vertex, an ant is crawls between the vertices of a regular octahedron. After reaching a vertex, it randomly picks a neighboring vertex (sharing an edge) and walks to that vertex along the adjoining edge (with all possibilities equally likely.) What is the probability that after walking along 2006 edges, the ant returns to the vertex where it began? 2005 2 +1 Answer: 2006 3 · 2 Solution: For each nonnegative integer n , let a , b , and c denote the respective n n n probabilities that the ant is where it began, at a neighbor of where it began, or is opposite where it began after moving along n edges. We seek a . We have a = 1 2006 0 and b = c = 0. We also have the recursive system 0 0 b n − 1 a = n 4 b n − 1 b = a + + c n n − 1 n − 1 2 b n − 1 c = n 4 b b n − 1 n − 2 for integers n ≥ 1. Substituting into the second equation we have b = + n 2 2 x 1 − 1 2 for n ≥ 2. Solving the characteristic equation x − − = 0 for x = 1 , , we write 2 2 2 n n b = a · 1 + b ( − 1 / 2) . Using b = 0 , b = 1, we compute n 0 1 2 n b = · (1 − ( − 1 / 2) ) n 3 ( ) 2005 b 1 1 2 +1 2005 From which we find a = = 1 + = . 2006 2005 2006 4 6 2 3 · 2