1
$\begingroup$

How many possible passwords of a four digit length contain at least one uppercase character and at least one number?

  • 95 total ACII Symbols
    • 26 uppercase letters
    • 26 lowercase letters
    • 10 numbers
    • 33 special characters

So I have calculated that there are $26$ possibilities for the uppercase letter digit and $10$ possibilities for the number digit and also a variation of all the other possibilites, thus:

$26 \cdot 10 \cdot |var_2([1,95])| = 26 \cdot 10 \cdot 95^2 =2 346 500$

Unfortunately this is the wrong solution. It should be $18700240$.

Question: Were is my mistake?

$\endgroup$
1
  • 3
    $\begingroup$ Your mistake is that you counted the number of passwords where the first character is upper case, the second character is a number, and your remaining two characters are anything. You neglected to count the password "3aBc" as well as neglected to count the password "133T" etc... For a correct solution, apply inclusion-exclusion. There are $95^4$ total passwords. $(95-26)^4$ of which contain no capital letters so we remove those from the count. $(95-10)^4$ of which contain no numbers so we remove those too, but in doing so the passwords with neither got removed twice so we correct it by... $\endgroup$
    – JMoravitz
    Mar 30, 2017 at 8:44

3 Answers 3

2
$\begingroup$

Your mistake is that you counted the number of passwords where the first character is upper case, the second character is a number, and your remaining two characters are anything. You neglected to count the password "3aBc" as well as neglected to count the password "133T" etc...

For a correct solution, apply inclusion-exclusion. There are $95^4$ total passwords. $(95-26)^4$ of which contain no capital letters so we remove those from the count. $(95-10)^4$ of which contain no numbers so we remove those too, but in doing so the passwords with neither got removed twice so we correct it by adding that amount back in.

In more detail, let $\Omega$ be the set of passwords of length $4$ using these $96$ characters with no other restrictions. Let $A$ be the set of passwords with no capital letters. Let $B$ be the set of passwords with no numbers.

We are tasked with counting $|A^c\cap B^c|$, i.e. the set of passwords where there is at least one capital letter and there is at least one number.

By demorgan's, $A^c\cap B^c = (A\cup B)^c = \Omega\setminus(A\cup B)$

We have then by inclusion-exclusion $$|A^c\cap B^c|=|\Omega\setminus(A\cup B)|=|\Omega|-|A|-|B|+|A\cap B|$$

We find $|\Omega|=95^4$, $|A|=(95-26)^4$, $|B|=(95-10)^4$, and $|A\cap B|=(95-26-10)^4$ each by straightforward application of multiplication principle.

The final total is then

$$95^4-69^4-85^4+59^4$$

$\endgroup$
2
  • $\begingroup$ What does the $c$ mean in $|A^c\cap B^c|$? $\endgroup$
    – jublikon
    Mar 30, 2017 at 9:38
  • $\begingroup$ @jublikon the complementary set. Given a universal set $\Omega$ one has $A^c:= \{x\in\Omega~:~x\notin A\}=\Omega\setminus A$ $\endgroup$
    – JMoravitz
    Mar 30, 2017 at 9:48
0
$\begingroup$

For one, this does not account for the possible variations of order.

Here's a short way to compute this: Let $\Omega$ denote the set of all passwords, $U$ denote the set of passwords that include no uppercase letter, and $N$ the set of passwords that include no digit. Then, the set of passwords that include an uppercase letter and a number is $$\Omega - (N \cup C),$$ so the number of passwords satisfying the criteria is $$|\Omega - (N \cup C)| = |\Omega| - |N \cup C| .$$ Now, use the Inclusion-Exclusion principle to evaluate $|N \cup C|$.

$\endgroup$
0
$\begingroup$

You have worked out the number of passwords that have, say, the first characters an uppercase letter and the second character a number. This does not allow for cases where, say, our first two spaces are lowercase characters and/or special characters and our uppercase letter and number fill the last two spaces of the password.

Because the question says "at least $1$" I would immediately be drawn to considering the the compliment case i.e. The passwords with no uppercase letters, no numbers or neither uppercase letters nor numbers.

$$\text{total unrestriced passwords}=95^4$$ $$\text{passwords with no uppercase letters}=(95-26)^4=69^4$$ $$\text{passwords with no numbers}=(95-10)^4=85^4$$ $$\text{passwords with no uppercase letters or numbers}=(95-26-10)^4=59^4$$

then by the principle of inclusion-exclusion we subtract the two complement cases from the total and add back their intersection:

$$\text{desired count}=95^4-(69^4+85^4)+59^4=18\,700\,240\tag{Answer}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .