Maths Olympiad Prep

Library / /1342 of 1394

Combinatorics Difficulty 6.1 National Olympiad Prove it United States

Problem:

Among citizens of Cambridge there exist 88 different types of blood antigens. In a crowded lecture hall are 256256 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 kk blood antigen foreign to him/her will suffer for kk hours. What is the expected total suffering of all 256256 students, in hours?

Solution

Solution:

Let n=8n=8.

First, consider any given student SS and an antigen aa foreign to him/her. Assuming SS has been bitten, we claim the probability SS will suffer due to aa is
122n1+1122n1(2n1+1) 1 - \frac{2^{2^{n-1}+1} - 1}{2^{2^{n-1}} (2^{n-1} + 1)}
Indeed, let N=2n1N = 2^{n-1} denote the number of students with aa. So considering just these students and summing over the number bitten, we obtain a probability
12Nt=0N(Nt)(Nt)tt+1=12N2NN2N+1N+1 \frac{1}{2^{N}} \sum_{t=0}^{N} \binom{N}{t} \binom{N}{t} \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)(S, a) of students SS and antigens aa foreign to them. Noting that each student is bitten with probability 12\frac{1}{2}, and retaining the notation N=2n1N=2^{n-1}, we get
12k=0n[(nk)k(2NN2N+12N(N+1))]=nN(2NN2N+1)2N+1(N+1). \frac{1}{2} \sum_{k=0}^{n} \left[ \binom{n}{k} \cdot k \left( \frac{2^{N} N - 2^{N} + 1}{2^{N}(N+1)} \right) \right] = \frac{n N (2^{N} N - 2^{N} + 1)}{2^{N+1}(N+1)}.
Finally, setting n=8=23n=8=2^{3} and N=2n1=27=128N=2^{n-1}=2^{7}=128, we get the claimed answer.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.