There are $33$ students. Several clubs are set up among them each one about either math or physics. Clubs with a single member are allowed.
For each $i\in[1,11]$ there exists at least one club with $i$ members, and each student is in exactly one math club and one physics club.
Show that there exists two students who share the same club in both subjects.
For the students in the same club we connect a line between them. So each club with $m$ members has correspondence with $\mbox C_m^2$ lines.
However if we use this kind of estimation we get there’re at least $\displaystyle\sum_{k=1}^{11}\mbox C_m^2<\mbox C_{33}^2 $ lines so it doesn’t work.
Now I guess this is because in the estimation only $\displaystyle\sum_{k=1}^{11}=33$ students are considered whereas the sum of members of all clubs($66$) is twice as much so lines get wasted a lot.
Can anyone improve the strategy?
Best Answer
The number of total memberships is: $1+2+3+\cdots + 11 = 66$, and each student is in exactly two clubs, so there are exactly $11$ clubs for $33$ students.
If $M$ is the number of maths clubs, then $11-M$ is the number of physics clubs.
The number of distinct pairs of one maths club and one physics club is $M(11-M)$, and
$$M(11-M) \le 5.5^2 = 30.25<33$$
So by pigeonhole, at least two students among the $33$ share the same clubs in both subjects.