HMMT 十一月 2013 · THM 赛 · 第 4 题

HMMT November 2013 — THM Round — Problem 4

[ 7 ] There are 2 runners on the perimeter of a regular hexagon, initially located at adjacent vertices. Every second, each of the runners independently moves either one vertex to the left, with probability 1 1 , or one vertex to the right, also with probability . Find the probability that after a 2013 second 2 2 run (in which the runners switch vertices 2013 times each), the runners end up at adjacent vertices once again.

解析

[ 7 ] There are 2 runners on the perimeter of a regular hexagon, initially located at adjacent vertices. Every second, each of the runners independently moves either one vertex to the left, with probability 1 1 , or one vertex to the right, also with probability . Find the probability that after a 2013 second 2 2 run (in which the runners switch vertices 2013 times each), the runners end up at adjacent vertices once again. 4027 2 1 1 2 +1 2 1 1 2 1 1 2013 4026 671 Answer: + ( ) OR OR + ( ) OR + ( ) Label the runners A and 4026 3 3 4 3 · 2 3 3 2 3 3 64 B and arbitrarily fix an orientation of the hexagon. Let p ( i ) be the probability that A is i (mod 6) t vertices to the right of B at time t , so without loss of generality p (1) = 1 and p (2) = · · · = p (6) = 0. 0 0 0 1 1 1 Then for t > 0, p ( i ) = p ( i − 2) + p ( i ) + p ( i + 2). t t − 1 t − 1 t − 1 4 2 4 In particular, p (2) = p (4) = p (6) = 0 for all t , so we may restrict our attention to p (1) , p (3) , p (5). t t t t t t 1 1 Thus p (1) + p (3) + p (5) = 1 for all t ≥ 0, and we deduce p ( i ) = + p ( i ) for i = 1 , 3 , 5. t t t t t − 1 4 4 Finally, let f ( t ) = p (1) + p (5) denote the probability that A, B are 1 vertex apart at time t , so t t 1 1 2 1 2 2 1 1 2013 f ( t ) = + f ( t − 1) = ⇒ f ( t ) − = [ f ( t − 1) − ], and we conclude that f (2013) = + ( ) . 2 4 3 4 3 3 3 4