HMMT 十一月 2010 · 团队赛 · 第 2 题

英文解析

2. [ 6 ] In terms of k , for k > 0 how likely is he to be back where he started after 2 k minutes?
   ( )
   1 3 1 k
   Answer: + Again, Travis starts at (0 , 0 , 0). At each step, exactly one of the three coordi-
   4 4 9
   nates will change. The parity of the sum of the three coordinates will change at each step, so after 2 ksteps, the sum of the coordinates must be even. There are only four possibilites for Travis’s position:
   (0 , 0 , 0), (1 , 1 , 0), (1 , 0 , 1), and (0 , 1 , 1). Let p be the probability that Travis is at (0 , 0 , 0) after 2 kksteps. Then 1 − p is the probability that he is on (1 , 1 , 0), (1 , 0 , 1), or (0 , 1 , 1). Suppose we want tokcompute p . There are two possibilities: we were either at (0 , 0 , 0) after 2 k steps or not. If we were,
   k +1
   th 1
   then there is a probability that we will return (since our (2 k + 1) step can be arbitary, but there isth th 13
   a chance that we will reverse that as our (2 k + 2) step). If we were not at (0 , 0 , 0) after our 2 kth 23
   steps, then two of our coordinates must have been ones. There is a probability that the (2 k + 1)
   th 13
   step will change one of those to a zero, and there is a step that that the (2 k + 2) step will change
   ( ) ( )3
   2 1 2
   the remaining one. Hence, in this case, there is a = probability that Travis ends up (0 , 0 , 0)
   3 3 9
   in this case. So we have:
   ( ) ( )
   1 2
   p = p + (1 − p )
   k +1 k k
   3 9
   1 2
   p = p +
   k +1 k
   9 9
   ( ) ( )
   1 1 1
   p − = p −
   k +1 k
   4 9 4
   1 1
   (We get the value either by guessing that the sequence p , p , p , ... should converge to or simply
   0 1 2
   4 4
   1 2 1 1
   by solving the equation − x + x = .) This shows that p − , p − , ... is a geometric series with
   0 1
   9 9 4 4
   ( ) ( )
   k k
   1 1 1 3 1 3 1 1 3 1
   ratio . Since p − = 1 − = , we get that p − = , or that p = + .
   0 k k
   9 4 4 4 4 4 9 4 4 9