5
How many eight character passwords are there if each character is either an    
uppercase letter A-Z, a lowercase letter a-z, or a digit 0-9, and where at    
least one character of each of the three types is used?

I believe this question is about using the technique of 'counting the complement'. The complement of "one character of each" is "either uppercase, lowercase, or digits is NOT used".

Total possible passwords : $62^8$

Total possible passwords w/ out uppercase letters: $36^8$

Total possible passwords w/ out lowercase letters: $36^8$

Total possible passwords w/ out digits : $52^8$

I think my trouble is from fully understanding what the 'complement' means. From what I understand it is (very loose explanation) the opposite of the restriction placed on our original set. So in our case the original set is $62^8$ and the complement of the restriction placed on that set, one of each character, is all the possibilities where types of characters are not there. Which are what I typed above this paragraph. However, I feel like I am missing something. Otherwise I would say that the answer is: $62^8 - [36^8 + 36^8 + 52^8]$.

Main problem: Not understanding how to compute the complement.

Ozera
  • 2,050
  • 1
    I think you've worked out what set the complement is without a problem, but you haven't got its size right. At the moment you're counting any password without lowercase letters or digits (for example) twice; once as a password without lowercase letters, and then again as a password without digits. You need to use the inclusion-exclusion principle here to count the complement. – mdp Jun 04 '13 at 10:13
  • I am counting it twice? I'm sorry, I don't think I am understanding. The passwords w/ out digits contain both lower/upper case. The passwords w/ out lowercase contain both digits/upper. Is that what you are referring to? – Ozera Jun 04 '13 at 10:40
  • I mean that if a password contains only lower case letters, you've counted it both as a password not containing digits, and as a password not containing upper case letters, so it gets subtracted off twice - once in one of the $36^8$s and once in the $52^8$ - Adriano's answer gives more details. – mdp Jun 04 '13 at 10:50

3 Answers3

4

As Matt commented, we are using the principle of inclusion-exclusion. Note that your expression so far: $$62^8 - [36^8 + 36^8 + 52^8]$$ is actually too small; you oversubtracted. This is because certain passwords were double counted. For example, consider the illegal password: $ABCDEFGH$. Certainly, this is a possible password (it belongs to the set of size $62^8$). However, it contains no lowercase letters (it belongs to one of the sets of size $36^8$), so it is subtracted. However, notice that it contains no digits (it belongs to the set of size $52^8$), so it is subtracted a second time. This is bad! This illegal password is being counted a total of $1-2=-1$ times!

To compensate, we must add some back in. Note that:

  • Total possible passwords without uppercase AND without digits: $26^8$
  • Total possible passwords without lowercase AND without digits: $26^8$
  • Total possible passwords without uppercase AND without lowercase: $10^8$

Returning to our example illegal password $ABCDEFGH$, notice that it contains no lowercase AND no digits (it belongs to one of the sets of size $26^8$), so it is added back in once. This is good! This illegal password is now counted a total of $1-2+1=0$ times in our final answer.

Hence, our total should actually be: $$62^8 - [36^8 + 36^8 + 52^8] + [26^8 + 26^8 + 10^8] = 159655911367680$$

EDIT: As Goos mentioned, we would normally continue this pattern by subtracting out the passwords without uppercase AND without lowercase AND without digits. In this case, however, this set has size $0^8$, so this doesn't affect the answer.

Adriano
  • 41,576
  • Ah I understand! Thank you! – Ozera Jun 04 '13 at 11:50
  • 1
    Normally, we would have to subtract back out the number of passwords with no uppercase letters, no lowercase letters, AND no digits. In this case of course there are 0 such passwords, but at the very least this should be mentioned. – Caleb Stanford Jun 04 '13 at 22:05
  • Goos, I know. When I was going through the problem I noticed this and wondered why I hadn't subtracted that out, but then I realized that there were no such passwords haha. – Ozera Jun 05 '13 at 09:10
2

For a set $X$ and a subset $A \subseteq X$, the complement (not compliment, which is a nice phrase about someone) is defined as $$ X \setminus A = \{ x \in X : x \notin A\}. $$

Then, when your set $A$ is defined as $$ A = \{ x \in X : \varphi(x) \} $$ where $\varphi(x)$ is an assumption about $x$ (we say a formula with free variable $x$), the complement is then easily computed by $$ X \setminus A = \{ x \in X : \neg \varphi(x)\} $$ (where $\neg$ is read "not").

In your case, the set $X$ is all 8-letter passwords on A-Z, a-z, 0-9, and, denoting the letters of a password $p$ by $p_1,\ldots,p_8$, the subset $A$ you're looking at is $$ A = \{ p \in X : \exists i,j,k,\ p_i \in \text{A-Z and } p_j \in \text{a-z and } p_k \in \text{0-9} \}. $$ Then, the complement is $$ X \setminus A = \{ p \in X : \forall i,j,k,\ p_i \notin \text{A-Z or } p_j \notin \text{a-z or } p_k \notin \text{0-9} \}, $$ that is the set of passwords such that any triple of letters does not meet A-Z, a-z and 0-9 simultaneously. So this is in fact the set of passwords without any uppercase or without any lowercase or without any digit.

So computing the cardinal $|X \setminus A|$ of $X \setminus A$, you get the cardinal $|A| = |X| - |X \setminus A|$ of the set $A$.

Pece
  • 11,584
0

I get 0.1620425383855200000E+15 = 162,042,538,385,520 using the algorithm derived at Derive an algorithm for computing the number of restricted passwords for the general case? .

Community
  • 1
user404757
  • 31
  • 1
  • 4
  • I think if you examine the approach used at http://math.stackexchange.com/questions/2103361/derive-an-algorithm-for-computing-the-number-of-restricted-passwords-for-the-gen#2103361 , you will find another method for solving the problem you state here. I would like to know if you agree with that approach and if you have any questions or comments about it. – user404757 Jan 19 '17 at 01:18
  • A blast from the past with this question. I'll examine the approach further, but I think its neat. – Ozera Feb 03 '17 at 22:26