HMMT 十一月 2010 · GEN1 赛 · 第 4 题

HMMT November 2010 — GEN1 Round — Problem 4

[ 4 ] An ant starts at the point (1 , 0). Each minute, it walks from its current position to one of the four adjacent lattice points until it reaches a point ( x, y ) with | x | + | y | ≥ 2. What is the probability that the ant ends at the point (1 , 1)? 6 5 4 3 2

解析

[ 4 ] An ant starts at the point (1 , 0). Each minute, it walks from its current position to one of the four adjacent lattice points until it reaches a point ( x, y ) with | x | + | y | ≥ 2. What is the probability that the ant ends at the point (1 , 1)? 7 1 1 Answer: From the starting point of (1 , 0), there is a chance we will go directly to (1 , 1), a 24 4 2 1 chance we will end at (2 , 0) or (1 , − 1), and a chance we will go to (0 , 0). Thus, if p is the probability 4 1 1 that we will reach (1 , 1) from (0 , 0), then the desired probability is equal to + p , so we need only 4 4 calculate p . Note that we can replace the condition | x | + | y | ≥ 2 by | x | + | y | = 2, since in each iteration the quantity | x | + | y | can increase by at most 1. Thus, we only have to consider the eight points (2 , 0), (1 , 1), (0 , 2), ( − 1 , 1), ( − 2 , 0), ( − 1 , − 1), (0 , − 2), (1 , − 1). Let p , p , ..., p be the probability of 1 2 8 General Test reaching each of these points from (0 , 0), respectively. By symmetry, we see that p = p = p = p 1 3 5 7 and p = p = p = p . We also know that there are two paths from (0 , 0) to (1 , 1) and one path from 2 4 6 8 (0 , 0) to (2 , 0), thus p = 2 p . Because the sum of all probabilities is 1, we have p + p + ... + p = 1. 2 1 1 2 8 1 1 1 Combining these equations, we see that 4 p +4 p = 12 p = 1, so p = and p = . Since p = p = , 1 2 1 1 2 2 12 6 6 1 1 1 7 then the final answer is + · = 4 4 6 24 6 5 4 3 2