Combinatorics problem with students choosing elective courses. (Prove by assuming the opposite). There are 2009 different elective courses in the university. Each one of the courses has exactly 45 students in it. Every 2 courses has exactly 1 student in common. Prove that there is a student enrolled in all courses.
I think it should be proven by assuming the opposite.
Maybe there is a connection that 2009/45 is less than 45 but I'm not sure about that.
 A: We will see the courses as a sets of students, where $x \in Y$ means that $x$ is enrolled in course $Y$ and $x = Y \cap Y'$ means that $x$ is the common student of $Y$ and $Y'$ (we omit curly braces around $x$).
We can prove the following lemma.
Lemma: There is a student enrolled in all courses, or each student is enrolled in at most 45 courses.
Proof: For a contradiction, let there be a student $a$ who is enrolled to more than $45$ courses, but not to all courses. The courses of $a$ will be denoted by $C_1, \dots C_k$, where $k > 45$. Let $C'$ be a course to which $a$ is not enrolled.
We have $\forall i \not = j < k: C_i \cap C_j = a$. Therefore, the student which a $C_i$ shares with $C'$ must be different for each $i$ (otherwise, the $|C_i \cap C_{i'}| > 1$). That is impossible by the pigeonhole principle ($C'$ have only $45$ students, while the range of $i$ is greater), which concludes the proof of the lemma.
$$\tag*{$\blacksquare$}$$
Thus, we may assume that each student is enrolled in at most $45$ courses, otherwise, we have the desired student.
Now, we can count the pairs $(\text{x}, \text{Y})$, such that the student $x$ is enrolled to course $Y$. Each course has exactly $45$ students, which gives $45 × 2009 = 90405$ pairs. However, each student can take up to $45$ courses by our assumption, which gives as most $45 × 45 = 2045$ pairs, which is a contradiction.
Therefore, the assumption regarding the maximal number of courses for a student cannot hold, which implies (by the lemma) that there is a student who took all courses.
$$\tag*{$\blacksquare$}$$
