CombinatoricsDifficulty 6.1National OlympiadProve itUnited States
Problem:
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
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−22n−1(2n−1+1)22n−1+1−1 Indeed, let N=2n−1 denote the number of students with a. So considering just these students and summing over the number bitten, we obtain a probability 2N1t=0∑N(tN)(tN)t+1t=2N1N+12NN−2N+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 21, and retaining the notation N=2n−1, we get 21k=0∑n[(kn)⋅k(2N(N+1)2NN−2N+1)]=2N+1(N+1)nN(2NN−2N+1). Finally, setting n=8=23 and N=2n−1=27=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.