The pigeonhole principle and a professor who knows $9$ jokes and tells $3$ jokes per lecture > 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.

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.