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

英文解析

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 numberof 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 randomlyi
    ∑ ∑
    chosen number in the range. By linearity of expectation, E ( R ) = E ( R ).
    i ii
    Since we choose every binary string of length 12 with equal probability, the sum of the expectationsis . However, this is not the expected number of 01 s and 10 s - we need to subtract the occasions 11
    where the leading digit is zero. There is a chance that the number starts with a 0, in which case we 12
    must ignore the first digit change - unless the number was 0, in which case there are no digit changes.2
    11 1 1 20481
    Therefore, our answer is − + = .
    2 2 4096 4096
    13 ANNUAL HARVARD-MIT MATHEMATICS TOURNAMENT, 20 FEBRUARY 2010 — GUTS ROUNDth