HMMT 二月 2008 · COMB 赛 · 第 9 题

英文解析

9. [ 7 ] On an infinite chessboard (whose squares are labeled by ( x, y ), where x and y range over all integers),
   a king is placed at (0 , 0). On each turn, it has probability of 0 . 1 of moving to each of the four edgeneighboring squares, and a probability of 0 . 05 of moving to each of the four diagonally-neighboringsquares, and a probability of 0 . 4 of not moving. After 2008 turns, determine the probability that theking is on a square with both coordinates even. An exact answer is required.
   1 3
   Answer: + Since only the parity of the coordinates are relevant, it is equivalent to
   2008
   4 4 · 5
   consider a situation where the king moves (1 , 0) with probability 0 . 2, moves (0 , 1) with probability 0 . 2,
   moves (1 , 1) with probability 0 . 2, and stays put with probability 0 . 4. This can be analyzed using thegenerating function
   2008
   (2 + x + y + xy )
   2008
   f ( x, y ) = (0 . 4 + 2 × 0 . 1 x + 2 × 0 . 1 y + 4 × 0 . 05 xy ) = .
   2008
   a b 5
   We wish to find the sum of the coefficients of the terms x y , where both a and b are even. Thisis simply equal to ( f (1 , 1) + f (1 , − 1) + f ( − 1 , 1) + f ( − 1 , − 1)). We have f (1 , 1) = 1 and f (1 , − 1) =1
   20084
   f ( − 1 , 1) = f ( − 1 , − 1) = 1 / 5 . Therefore, the answer is
   ( )
   1 1 3 1 3
   ( f (1 , 1) + f (1 , − 1) + f ( − 1 , 1) + f ( − 1 , − 1)) = 1 + = + .
   2008 2008
   4 4 5 4 4 · 5 3