HMMT 十一月 2010 · 团队赛 · 第 2 题
HMMT November 2010 — Team Round — Problem 2
题目详情
- [ 6 ] In terms of k , for k > 0 how likely is he to be back where he started after 2 k minutes?
解析
- [ 6 ] In terms of k , for k > 0 how likely is he to be back where he started after 2 k minutes? ( ) k 1 3 1 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 k steps, 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 k k steps. Then 1 − p is the probability that he is on (1 , 1 , 0), (1 , 0 , 1), or (0 , 1 , 1). Suppose we want to k compute p . There are two possibilities: we were either at (0 , 0 , 0) after 2 k steps or not. If we were, k +1 1 th then there is a probability that we will return (since our (2 k + 1) step can be arbitary, but there is 3 1 th th a chance that we will reverse that as our (2 k + 2) step). If we were not at (0 , 0 , 0) after our 2 k 3 2 th steps, then two of our coordinates must have been ones. There is a probability that the (2 k + 1) 3 1 th 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