# What is the minimum number of passwords needed to guarantee that at least $2$ passwords have the same number of lower case letters?

Need help with this pigeonhole principle based problem:

Assume computer passwords are between $6$ and $8$ characters long. Each character can be either an upper case letter, a lower case letter or a digit. Assume each password must have at least one upper case letter, at least one lower case letter and at most one digit.

Let $S$ be the set of passwords. What is the minimum cardinality of $S$ to guarantee that at least $2$ passwords in $S$ have the same number of lower case letters?

• Look at all possibilities with 1 lowercase. 6 chars = (D, 4U, L) or (5U, L) ; 7 chars = (D, 5U, L) or (6U, L); 8 chars = (D, 6U, L) or (7U, L). The next possibility will include a second lowercase. – sku Apr 3 '18 at 6:58

## 1 Answer

• The least number of lower case letters a password can have is $1$.
• The greatest number of lower case letters a password can have is $7$, i.e. when the password is $8$ letters long and has $1$ upper case letter and $0$ digits.

Now use the pigeonhole principle. When the cardinality of $S$ equals $7$, the worst case scenario is when each of the passwords in $S$ distinctly has one of the $7$ possible numbers of lower case letters. If we add $1$ more password to $S$, then $S$ is guaranteed to contain $2$ passwords that have the same number of lower case letters. Hence, the minimum cardinality of $S$ is $8$.