HMMT 二月 2016 · COMB 赛 · 第 2 题

HMMT February 2016 — COMB Round — Problem 2

Starting with an empty string, we create a string by repeatedly appending one of the letters H , M , 1 1 1 T with probabilities , , , respectively, until the letter M appears twice consecutively. What is the 4 2 4 expected value of the length of the resulting string?

解析

Starting with an empty string, we create a string by repeatedly appending one of the letters H , M , 1 1 1 T with probabilities , , , respectively, until the letter M appears twice consecutively. What is the 4 2 4 expected value of the length of the resulting string? Proposed by: Answer: 6 Let E be the expected value of the resulting string. Starting from the empty string, 1 • We have a chance of not selecting the letter M ; from here the length of the resulting string is 2 1 + E . 1 • We have a chance of selecting the letter M followed by a letter other than M , which gives a 4 string of length 2 + E . 1 • We have a chance of selecting M twice, for a string of length 2. 4 1 1 1 Thus, E = (1 + E ) + (2 + E ) + (2). Solving gives E = 6. 2 4 4