返回题库

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

HMMT February 2020 — Guts Round — Problem 31

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [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?
解析

英文解析

  1. [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