HMMT-Feb 2016 guts, Problem 28

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?

Solution: 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 \[ 1-\frac{2^{2^{n-1}+1}-1}{2^{2^{n-1}}\left(2^{n-1}+1\right)} \] Indeed, let $N=2^{n-1}$ denote the number of students with $a$. So considering just these students and summing over the number bitten, we obtain a probability \[ \frac{1}{2^{N}} \sum_{t=0}^{N}\left(\begin{array}{c} N \\ t \end{array}\right)\left(\begin{array}{c} N \\ t \end{array}\right) \frac{t}{t+1}=\frac{1}{2^{N}} \frac{2^{N} N-2^{N}+1}{N+1} \] We now use linearity over all pairs $(S, a)$ of students $S$ and antigens $a$ foreign to them. Noting that each student is bitten with probability $\frac{1}{2}$, and retaining the notation $N=2^{n-1}$, we get \[ \frac{1}{2} \sum_{k=0}^{n}\left[\left(\begin{array}{l} n \\ k \end{array}\right) \cdot k\left(\frac{2^{N} N-2^{N}+1}{2^{N}(N+1)}\right)\right]=\frac{n N\left(2^{N} N-2^{N}+1\right)}{2^{N+1}(N+1)} \] Finally, setting $n=8=2^{3}$ and $N=2^{n-1}=2^{7}=128$, we get the claimed answer. $\fbox{\frac{2^{135}-2^{128}+1}{2^{119} \cdot 129}}$.

Answer: \frac{2^{135}-2^{128}+1}{2^{119} \cdot 129}