HMMT 二月 2020 · 冲刺赛 · 第 31 题

HMMT February 2020 — Guts Round — Problem 31

[18] Anastasia is taking a walk in the plane, starting from (1 , 0). Each second, if she is at ( x, y ), she 1 moves to one of the points ( x − 1 , y ), ( x + 1 , y ), ( x, y − 1), and ( x, y + 1), each with probability. She 4 stops as soon as she hits a point of the form ( k, k ). What is the probability that k is divisible by 3 when she stops?

解析

[18] Anastasia is taking a walk in the plane, starting from (1 , 0). Each second, if she is at ( x, y ), she 1 moves to one of the points ( x − 1 , y ), ( x + 1 , y ), ( x, y − 1), and ( x, y + 1), each with probability. She 4 stops as soon as she hits a point of the form ( k, k ). What is the probability that k is divisible by 3 when she stops? Proposed by: Michael Ren √ 3 − 3 1 √ Answer: or 1 − 3 3 Solution: The key idea is to consider ( a + b, a − b ), where ( a, b ) is where Anastasia walks on. Then, the first and second coordinates are independent random walks starting at 1, and we want to find the probability that the first is divisible by 3 when the second reaches 0 for the first time. Let C be the n n th Catalan number. The probability that the second random walk first reaches 0 after 2 n − 1 steps is ( ) ∑ C 2 n − 1 n − 1 1 , and the probability that the first is divisible by 3 after 2 n − 1 steps is 2 n − 1 2 n − 1 i ≡ n mod 3 2 2 i (by letting i be the number of − 1 steps). We then need to compute ( ) ( ) ∞ ∑ ∑ C 2 n − 1 n − 1 . 2 n − 1 4 i n =1 i ≡ n mod 3 By a standard root of unity filter, ( ) n ∑ 2 n − 1 4 + 2 = . i 6 i ≡ n mod 3 Letting ∞ ∑ 2 n P ( x ) = √ = C x n 1 + 1 − 4 x n =0 be the generating function for the Catalan numbers, we find that the answer is √ ( ) ( ) 1 1 1 1 1 1 2 3 − 3 √ P + P = + · = . 6 4 12 16 3 12 3 3 1 + 4