3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sku Apr 3 '18 at 6:58
2
$\begingroup$
  • 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.