HMMT 二月 2016 · 冲刺赛 · 第 28 题
HMMT February 2016 — Guts Round — Problem 28
题目详情
- [ 14 ] Among citizens of Cambridge there exist 8 different types of blood antigens. In a crowded lecture hall 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 any antigens that student had. A student bitten while Quito had k blood antigen foreign to him/her will suffer for k hours. What is the expected total suffering of all 256 students, in hours? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2016, February 20, 2016 — GUTS ROUND Organization Team Team ID#
解析
- [ 14 ] Among citizens of Cambridge there exist 8 different types of blood antigens. In a crowded lecture hall 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 any antigens that student had. A student bitten while Quito had k blood antigen foreign to him/her will suffer 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: 119 2 · 129 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 is n − 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 and summing over the number bitten, we obtain a probability ( )( ) N N N ∑ 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 that 1 n − 1 each student is bitten with probability , and retaining the notation N = 2 , we get 2 [( ) ( )] n N N N N ∑ 1 n 2 N − 2 + 1 nN (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.