HMMT 二月 2010 · 冲刺赛 · 第 15 题

HMMT February 2010 — Guts Round — Problem 15

[ 8 ] Pick a random integer between 0 and 4095, inclusive. Write it in base 2 (without any leading zeroes). What is the expected number of consecutive digits that are not the same (that is, the expected number of occurrences of either 01 or 10 in the base 2 representation)? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUND

解析

[ 8 ] Pick a random integer between 0 and 4095, inclusive. Write it in base 2 (without any leading zeroes). What is the expected number of consecutive digits that are not the same (that is, the expected number of occurrences of either 01 or 10 in the base 2 representation)? 20481 Answer: Note that every number in the range can be written as a 12-digit binary string. For 4096 i = 1 , 2 , . . . 11, let R be a random variable which is 1 if the i th and ( i + 1)st digits differ in a randomly i ∑ ∑ chosen number in the range. By linearity of expectation, E ( R ) = E ( R ). i i i Since we choose every binary string of length 12 with equal probability, the sum of the expectations 11 is . However, this is not the expected number of 01s and 10 s - we need to subtract the occasions 2 1 where the leading digit is zero. There is a chance that the number starts with a 0, in which case we 2 must ignore the first digit change - unless the number was 0, in which case there are no digit changes. 11 1 1 20481 Therefore, our answer is − + = . 2 2 4096 4096 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th 13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUND