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

英文解析

28. [ 14 ] Among citizens of Cambridge there exist 8 different types of blood antigens. In a crowded lecturehall are 256 students, each of whom has a blood type corresponding to a distinct subset of the antigens;
    the remaining of the antigens are foreign to them.
    Quito the Mosquito flies around the lecture hall, picks a subset of the students uniformly at random,
    and bites the chosen students in a random order. After biting a student, Quito stores a bit of anyantigens that student had. A student bitten while Quito had k blood antigen foreign to him/her willsuffer for k hours. What is the expected total suffering of all 256 students, in hours?
    Proposed by: Sammy Luo
    135 128
    2 − 2 +1
    Answer:
    2 · 129119
    Let n = 8.
    First, consider any given student S and an antigen a foreign to him/her. Assuming S has been bitten,
    we claim the probability S will suffer due to a isn − 1
    2 +1
    2 − 1
    1 − .
    n − 1
    2 n − 1
    2 (2 + 1)
    n − 1
    Indeed, let N = 2 denote the number of students with a . So considering just these students andsumming over the number bitten, we obtain a probability
    ( )( )
    N NN
    ∑
    1 N N t 1 2 N − 2 + 1 = .
    N N
    2 t t t + 1 2 N + 1
    t =0
    We now use linearity over all pairs ( S, a ) of students S and antigens a foreign to them. Noting thatn − 11
    each student is bitten with probability , and retaining the notation N = 2 , we get
    [( ) ( )]2
    N N N Nn
    ∑
    1 n 2 N − 2 + 1 n n (2 N − 2 + 1)
    · k = .
    N N +1
    2 k 2 ( N + 1) 2 ( N + 1)
    k =0
    3 n − 1 7
    Finally, setting n = 8 = 2 and N = 2 = 2 = 128, we get the claimed answer.