The pigeonhole principle and a professor who knows $9$ jokes and tells $3$ jokes per lecture

Question

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.

Answer 1

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.

Answer 2

Notice, that there are $\binom{9}{2}=36$ unique pairs of jokes.

In every lecture there are three jokes (A, B and C), thus there are three unique pairs (AB, AC, BC) per lecture used.

In series of 13 lectures there are $13*3=39$ pairs of used jokes. Thus, after the pigeonhole principle, at least one of the unique pair is used at least twice.

Answer 3

In each one of the $13$ lectures, the professor can choose from a total of ${9 \choose 3 } = 84$ different combinations of jokes.

And, in each particular one of these $84$ combinations, there are ${ 3 \choose 2 } = 3$ distinct pairs.

Thus in each one of the $13$ lectures, there are $84 \times 3 = 252$ different pairs of jokes possible.

On the other hand, there are only ${ 9 \choose 2} = 36$ different pairs of jokes that could possibly be chosen from a total of $9$ jokes.

Hence we must have repetitions.

Hope this helps.

Answer 4

Sometimes it is a bit easier to prove a bit more: We can actually show that the joke that has been told most often must be in the pair of jokes that we are looking for.

There will be at least one joke that has been told at least 5 times: There are $13\cdot3$ slots for jokes and if each joke was told at most 4 times, 9 jokes could only fill $9\cdot 4$ slots, but $13\cdot 3 > 9\cdot 4$. (Indeed I calculated: With 12 days each joke would be told an average $\frac{12\cdot3}9=\frac{12}3=4$ times, so with one day more at least one joke has to be told more than 4 times.)

Now if we restrict our attention to only the days on which that joke has been told, then of the other 8 jokes, at least one has been told twice: We have (at least) $5\cdot2$ slots to fill, and that is more than $8$.

Answer 5

Let $a_1,a_2,a_3$ be the jokes he told on first day. To tell jokes for 13 days,without running out of jokes he has to tell jokes efficiently.

So he takes one joke from first day and repeats it. Second day jokes are {$a_1,a_4,a_5$ } ...like that maximum number of days he can do that is=(9-1)/2=4 days

Now he fixes $a_2$,repeat the above process without including $a_1,a_3$. Maximum number of days he can do that is=(9-3)/2=3 days.

Repeating this,we get maximum number days he can afford to tell joke=4+3+2+1=10 days

Answer 6

(Please forgive my inexperience with using MathJax)
It should be assumed that the professor never tells the same joke twice in a single lecture. I think this is reasonable, and it seems that other respondents are also assuming this. If a joke can be repeated during a lecture, then I think it adds a layer of complexity to the problem that is uncharacteristic of traditional pigeonhole principle problems.

Amount of possible joke-pairs = ${9 \choose 2}$ = 72.
Amount of joke-pairs told during a lecture = ${3 \choose 2}$ = 3. This is the first-third joke pairing, the first-second joke pairing, and the second-third joke pairing.
Total amount of joke-pairs that occur = 13 lectures * 3 per lecture = 39.

According to the pigeonhole principle. If 72 > 39, then at least one joke-pair will be repeated.