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 ), shemoves to one of the points ( x − 1 , y ), ( x + 1 , y ), ( x, y − 1), and ( x, y + 1), each with probability. She 1
stops as soon as she hits a point of the form ( k, k ). What is the probability that k is divisible by 3 when 4
she stops?
解析
英文解析
- [18] Anastasia is taking a walk in the plane, starting from (1 , 0). Each second, if she is at ( x, y ), shemoves to one of the points ( x − 1 , y ), ( x + 1 , y ), ( x, y − 1), and ( x, y + 1), each with probability. She 1
stops as soon as she hits a point of the form ( k, k ). What is the probability that k is divisible by 34
when she stops?
Proposed by: Michael Ren
√
3 − 3 1
√
Answer: or 1 −
Solution: The key idea is to consider ( a + b, a − b ), where ( a, b ) is where Anastasia walks on. Then,33
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 then th Catalan number. The probability that the second random walk first reaches 0 after 2 n − 1 steps isn
( )
∑
2 n − 1Cn − 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 in =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
∞
∑
n 2
P ( x ) = √ = C xn
1 + 1 − 4 xn =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
1 +3 4