$33$ students in clubs

Question

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?

Answer 1

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.

Answer 2

You did a silly and thought $\displaystyle\sum_{k=1}^{11} k=33$ but actually $\displaystyle\sum_{k=1}^{11} k=66.$ So now try the problem for yourself again and see if you get it before reading my solution below.

Since for all $i\in [1,11]$, there exists at least one club with $i$ members, $\displaystyle\sum_{k=1}^{11}k =66 = 33\times 2:$ Therefore $\displaystyle\sum_{k=1}^{11}k $ describes all of the clubs: there are exactly $11$ clubs: one with one member, one with two members, ..., one with ten members, one with eleven members.

Each of the people in the $11-$ member club (assume it's a Physics club) belong to another club- for each person their other club must be a maths club. So we have $11$ people in at most $10$ maths clubs: so by PHP at least two of them must be in the same maths club and we are done.