HMMT 二月 2016 · 冲刺赛 · 第 25 题

英文解析

25. [ 14 ] A particular coin can land on heads (H), on tails (T), or in the middle (M), each with proba-
    bility . Find the expected number of flips necessary to observe the contiguous sequence HMMTH-1
    MMT...HMMT, where the sequence HMMT is repeated 2016 times.3
    Proposed by: Ritesh Ragavender
    8068
    3 − 81
    Answer:
    Let E be the expected number of flips needed. Let E be the expected number more of flips needed 80
    0 1
    if the first flip landed on H. Let E be the expected number more if the first two landed on HM. Ingeneral, let E be the expected number more of flips needed if the first k flips landed on the first k 2
    values of the sequence HMMTHMMT...HMMT.k
    We have
    {
    1 1 1
    1 + E + E + E i 6 ≡ 0 (mod 4)
    i +1 1 0
    3 3 3
    E =
    1 2 i
    1 + E + E i ≡ 0 (mod 4)
    i +1 0
    3 3
    Using this relation for i = 0 gives us E = E − 3 . Let F = E . By simple algebraic manipulations 1
    1 0 i i iwe have 3
    {
    − · E i 6 ≡ 0 (mod 4)2
    i +1 0
    F − F =3
    i +1 i
    1 2 − − · E i ≡ 0 (mod 4)
    i i +1 0
    3 3
    We clearly have F = 0 and F = E . So adding up the above relations for i = 0 to i = 2016 · 4 − 1
    2016 · 4 0 0
    gives
    2016 · 4 2015
    ∑ ∑
    1 1 − E = − 2 E −
    0 0
    i 4 k
    3 3
    i =1 k =0
    ( )
    1 −1
    2016 · 41 = E − 1 −3
    2016 · 4800
    8068813
    3 − 81
    so E = .
    a ↑↑ ( b − 1)800