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

HMMT February 2016 — Guts Round — Problem 25

[ 14 ] A particular coin can land on heads (H), on tails (T), or in the middle (M), each with proba- 1 bility . Find the expected number of flips necessary to observe the contiguous sequence HMMTH- 3 MMT...HMMT, where the sequence HMMT is repeated 2016 times. a ↑↑ ( b − 1)

解析

[ 14 ] A particular coin can land on heads (H), on tails (T), or in the middle (M), each with proba- 1 bility . Find the expected number of flips necessary to observe the contiguous sequence HMMTH- 3 MMT...HMMT, where the sequence HMMT is repeated 2016 times. Proposed by: Ritesh Ragavender 8068 3 − 81 Answer: 80 Let E be the expected number of flips needed. Let E be the expected number more of flips needed 0 1 if the first flip landed on H. Let E be the expected number more if the first two landed on HM. In 2 general, let E be the expected number more of flips needed if the first k flips landed on the first k k values of the sequence HMMTHMMT...HMMT. We have { 1 1 1 1 + E + E + E i 6 ≡ 0 (mod 4) i +1 1 0 3 3 3 E = i 1 2 1 + E + E i ≡ 0 (mod 4) i +1 0 3 3 1 Using this relation for i = 0 gives us E = E − 3 . Let F = E . By simple algebraic manipulations 1 0 i i i 3 we have { 2 − · E i 6 ≡ 0 (mod 4) i +1 0 3 F − F = 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 − 1 2016 · 4 3 = E − 1 − 0 80 2016 · 4 3 81 8068 3 − 81 so E = . 0 80 a ↑↑ ( b − 1)