返回题库

HMMT 二月 2020 · COMB 赛 · 第 10 题

HMMT February 2020 — COMB Round — Problem 10

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

题目详情

英文原题

  1. Max repeatedly throws a fair coin in a hurricane. For each throw, there is a 4% chance that the coingets blown away. He records the number of heads H and the number of tails T before the coin is lost.
    (If the coin is blown away on a toss, no result is recorded for that toss.) What is the expected value of
    | H − T | ?
解析

英文解析

  1. Max repeatedly throws a fair coin in a hurricane. For each throw, there is a 4% chance that the coingets blown away. He records the number of heads H and the number of tails T before the coin is lost.
    (If the coin is blown away on a toss, no result is recorded for that toss.) What is the expected value of
    | H − T | ?
    Proposed by: Krit Boonsiriseth
    Answer:24
    Solution 1: (Dilhan Salgado) In all solutions, p = will denote the probability that the coin is 17
    blown away. Let D = | H − T | . Note that if D 6 = 0, the expected value of D is not changed by a 25
    coin flip, whereas if D = 0, the expected value of D increases by 1. Therefore E ( D ) can be computedas the sum over all n of the probability that the n th coin flip occurs when D = 0. This only occurs
    2 k +1
    when n = 2 k + 1 is odd, where the probability that the first n coin flips occur is (1 − p ) and the
    2 k
    ( )
    probability that D = 0 after the first n − 1 flips is . Thereforekk
    ( ) ( )4
    ∞
    2 k
    ∑
    1 − p 2 k
    E ( D ) = (1 − p )
    2 kk =0
    1 − p
    √
    2=
    1 − (1 − p )
    using the generating function
    ( )
    ∞
    ∑
    2 k 1
    x = √ .kk
    1 − 4 xk =0
    1 24
    Plugging in p = yields E ( D ) = .
    25 7
    Solution 2: For each n > 0, the probability that Max made n successful throws (not counting thenlast throw) is p (1 − p ) .
    Claim: Assuming Max made n > 1 throws, the expected value of | H − T | is given byb ( n − 1) / 2 c
    ∏
    2 k + 1
    .
    2 kk =1
    Proof. If n is odd then the expected value for n + 1 will be equal to that for n ; since | H − T | will benonzero, it will be equally likely to increase or decrease after the coin is flipped. Therefore, it sufficesto compute the expected value for the n odd case. This is
    ( ) ( )
    ∑ ∑
    ( n − 1) / 2 ( n − 1) / 2
    n n
    · ( n − 2 i ) · 2 ii =0 i =0
    i i = n −
    n − 1 n − 1
    2 2
    ( )
    ( )
    ∑
    ( n − 3) / 2
    n − 1
    2 ·
    i =0 = n · 1 −in − 1
    ( )2
    n − 1
    ( n − 1) / 2 = n ·
    n − 1
    n !2
    2=
    ( n − 1)!!
    n !!
    ( n − 1)!!=
    ( n − 1) / 2
    ∏
    2 k + 1 = ,
    2 kk =1
    as desired.
    Using the claim, we have
     
    b ( n − 1) / 2 c
    ∞
    ∑ ∏
    2 k + 1
     n
    E ( | H − T | ) = p (1 − p )
    2 kn =1
    k =1
    ( )
    ∞ m
    ∑ ∏
    2 k + 1
    2 m = p (1 − p )(2 − p ) (1 − p )
    2 km =0
    k =1
    ( ) − 3 / 2 = p (1 − p )(2 − p ) 1 − (1 − p )2
    1 − p
    √
    = .
    p (2 − p )
    Plugging in p = gives 1
    24 5 2425
    E ( | H − T | ) = · 5 · = .
    25 7 7
    Solution 3: Let E be the expected value of | H − T + n | . By symmetry, E = E for all n .
    n − n n
    Considering what happens in the next throw gives
    2 E = (1 − p ) E + (1 − p ) E + 2 pnn n − 1 n +1
    √
    1 − p (2 − p )
    for all n > 0. Now let α = < 1 be the smaller root of (1 − p ) x − 2 x + (1 − p ) = 0. From 2
    1 − p
    ∞ ∞
    ∑ ∑
    n n
    2 α E = α ((1 − p ) E + (1 − p ) E + 2 pn )
    n n − 1 n +1
    n =1 n =1
    ∞ ∞
    ∑ ∑
    ( )
    2 n n − 1 n +1 = α (1 − p ) E + α (1 − p ) E + 2 pnα + (1 − p ) α + (1 − p ) α ) E
    0 1 nn =1 n =2
    ∞ ∞
    ∑ ∑
    n n = α (1 − p ) E + (2 α − (1 − p )) E + 2 pnα + 2 α E ,
    0 1 nn =1 n =2
    we have
    ∞
    ∑
    2 pαn
    (1 − p ) E − α (1 − p ) E = 2 pnα = .
    1 0
    (1 − α )2
    n =1
    As E = (1 − p ) E , this gives
    0 1
    2 pα
    E (1 − α (1 − p )) = .
    (1 − α )20
    1 3 24
    Plugging in p = and α = gives E = .
    25 4 70