Pigeon-Hole Probability principle

958 Views Asked by At

I am trying to solve the following question:

Consider a list of randomly generated lowercase $3$-letter "words" printed on a paper. The letters cannot be repeated.

So, then I deduced that there must be $$\begin{pmatrix}26 \\ 1\end{pmatrix}+\begin{pmatrix}25 \\ 1\end{pmatrix} + \begin{pmatrix}24 \\ 1\end{pmatrix}$$ unique words.

However, if I want to figure out how many words must be printed in order to have at least $3$ identical "words" on the list, I am not exactly sure what that means. How can you have identical words? In which case, wouldn't that be extra counting in the original computation of the number of $3$ letter words to begin with?

1

There are 1 best solutions below

4
On BEST ANSWER

So first off the sentence "The letters cannot be repeated" must mean that within a single word no repetition is allowed. This gives you $$ 3!\binom{26}{3}=6\times2600=15600 $$ unique words to begin with. Then if you print more than $2\cdot 15600$ words, then by the Pigeon Hole Principle, at least one of the words must be repeated three times in the list, so the answer is that when $$ 2\cdot15600+1=31201 $$ words are printed at least one of the words is repeated three times.