A professor knows $9$ jokes and tells $3$ jokes per lecture.
Prove that in a course of $13$ lectures there is going to be a pair of jokes that will be told together in at least $2$ lectures.
I've started with counting how many possibilities there are to tell jokes in a lecture. Let
$$J := \{1,2,\dots,9\}$$
The amount of all different possible combinations for jokes is $9 \choose 3$ and for each lecture there are going to be $3$ unique pairs of jokes $\left(\frac{3!}{2!}=3\right)$.
I'm not sure how to continue from here to get to the PHP, I think I might be doing something wrong here, any advice how to abstract it properly?
This is an exercise from the Tel-Aviv University entry test preparation and I'm not a student yet so elementry combinatorics should do here.
Best Answer
I will assume that he doesn't tell the same joke twice (or three times) in the same lecture. Else, here is a counterexample:
Let $\{a_1, \ldots, a_9\}$ be the set of jokes. On the $i$-th day for $1 \leq i \leq 9$, tell jokes $(a_i, a_i, a_i)$. Then tell $(a_1, a_2, a_3)$, $(a_4, a_5, a_6)$, $(a_7, a_8, a_9)$ and $(a_1, a_4, a_7)$.
So, now towards the exercise. Every day the professor tells $3$ distinct pairs of jokes. Which means in total he tells $39$ pairs of jokes over the $13$ days. There are $\frac{9!}{7!2!}= 36$ pairs of jokes he can tell. So he must tell at least one pair of jokes twice.