HMMT 二月 2012 · 冲刺赛 · 第 25 题

HMMT February 2012 — Guts Round — Problem 25

[ 17 ] FemtoPravis is walking on an 8 × 8 chessboard that wraps around at its edges (so squares on the left edge of the chessboard are adjacent to squares on the right edge, and similarly for the top and bottom edges). Each femtosecond, FemtoPravis moves in one of the four diagonal directions uniformly at random. After 2012 femtoseconds, what is the probability that FemtoPravis is at his original location?

解析

[ 17 ] FemtoPravis is walking on an 8 × 8 chessboard that wraps around at its edges (so squares on the left edge of the chessboard are adjacent to squares on the right edge, and similarly for the top and bottom edges). Each femtosecond, FemtoPravis moves in one of the four diagonal directions uniformly at random. After 2012 femtoseconds, what is the probability that FemtoPravis is at his original location? ( ) 2 1005 1+2 Answer: We note the probability that he ends up in the same row is equal to the 1007 2 probability that he ends up in the same column by symmetry. Clearly these are independent, so we calculate the probability that he ends up in the same row. Now we number the rows 0 − 7 where 0 and 7 are adjacent. Suppose he starts at row 0. After two 1 1 more turns, the probability he is in row 2 (or row 6) is , and the probability he is in row 0 again is . 4 2 Let a , b , c and d denote the probability he is in row 0,2,4,6 respectively after 2 n moves. n n n n We have a = 1, and for n ≥ 0 we have the following equations: 0 1 1 1 a = a + b + d n +1 n n n 2 4 4 1 1 1 b = b + a + c n +1 n n n 2 4 4 1 1 1 c = c + b + d n +1 n n n 2 4 4 1 1 1 d = d + a + c n +1 n n n 2 4 4 From which we get the following equations: 1 a + c = n n 2 1 x n − 1 x = a − c = ( a − c ) = n n n n − 1 n − 1 2 2 So 1 a + c = 1006 1006 2 1 x = 1 , x = 0 1006 1006 2 1005 1 + 2 a = 1006 1007 2 ( ) 2 1005 1+2 And thus the answer is . 1007 2