There are exactly $120$ Twitter subscribers from National Science High School. Statistics show that each of $10$ given celebrities has at least $85$ followers from National Science High School. Prove that there must be two students such that each of the $10$ celebrities is being followed in Twitter by at least one of these students.
Problem
Source:
Tags: combinatorics unsolved, combinatorics
henry24816
04.09.2016 15:37
Given a random pair of students, and any celebrity, the probability that the celebrity is not being followed by either one of these students is $\left(\frac{120-85}{120}\right)^2=(7/24)^2 = 49/576$. Therefore, by linearity of expectation, the expected total number of celebrities that is not being followed by each pair is $10 \cdot \frac{49}{576} <1$. So the expected number of celebrities followed by at least one of these students is between 9 and 10. Since this is an average, there must exist a pair such that each of the celebrities is followed by at least one of these students.
Snap! Snap! Clap! Clap!
Takeya.O
04.11.2016 04:59
Since $\frac{85\cdot 10}{120}>7,$there exists a student A who follows $8$ celebrities.On the other hand,we consider $119$ students except for student A.Left $2$ celebrities are followed by at least $84$ students.Since $84\cdot 2>119,$there exists a student B who follows both $2$ celebrities.Therefore students A and B satisfy the condition and completing the proof.$\blacksquare$