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

英文解析

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 verticesonce 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)
   vertices to the right of B at time t , so without loss of generality p (1) = 1 and p (2) = · · · = p (6) = 0.t
   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 , sot 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