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

英文解析

17. 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) andwalks 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 respectiven n nprobabilities that the ant is where it began, at a neighbor of where it began, or isopposite 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
    n − 1 ba =
    4 nbn − 1
    b = a + + cn n − 1 n − 1
    b 2
    n − 1
    c =
    4 nb bn − 1 n − 2
    for integers n ≥ 1. Substituting into the second equation we have b = +
    2 2 nx 1 − 1
    for n ≥ 2. Solving the characteristic equation x − − = 0 for x = 1 , , we write 2
    2 2 2
    n nb = a · 1 + b ( − 1 / 2) . Using b = 0 , b = 1, we computen 0 1
    n 2
    b = · (1 − ( − 1 / 2) )
    3 n
    ( )
    2005
    b 1 1 2 +1
    2005
    From which we find a = = 1 + = .
    2006 2005 2006
    4 6 2 3 · 2