2
$\begingroup$

I'm working from Kenneth Rosen's book "Discrete Mathematics and its applications (7th edition)". One of the topics is counting, he gives an example of how to count the total number of possible passwords.

Question: Each user on a computer system has a password, which is six to eight characters long, where each character is an uppercase letter or digit. Each password must contain at least one digit. How many possible passwords are there?

His solution: Let $P$ be the total number of possible passwords, and let $p_6, p_7$ and $p_8$ denote the number of possible passwords of length 6, 7, and 8, respectively. By the sum rule, $p = p_6 + p_7 + p_8$.

$P_6 = 36^6 - 26^6 = 2,176,782,336 - 1,308,915,776 = 1,867,866,560$

Similar process for $p_7$ and $p_8$.

This is where I'm confused, what is the logic for finding $p_6$? If I was given the question, I would have done as follows:

$p_6 = 36^5 * 10$, because 5 of the 6 characters can be a letter or a number, so 36 possible values for each character. One character has to be numerical, so it has 10 possible values. All multiplied together, gives you $p_6$. Obviously I'm wrong, but why is he right?

I'd just like to understand the thinking behind Rosen's solution, as he does not make that clear in the book.

$\endgroup$
2
$\begingroup$

He is computing the number of passwords if there were no restriction ($36^6$) less the number of passwords made up only of letters ($26^6$).

Your computation doesn't take into account the position of the number within the password, or the fact that there can be more than one number (and therefore you have to be careful about double-counting).

$\endgroup$
1
$\begingroup$

The number of passwords with at least one digit plus the number of passwords with no digit equals the total number of passwords.

$\endgroup$
1
$\begingroup$

Hint: But however, it is not given that the password should contain atleast one uppercase letter.


Thus, each of the six spaces can be occupied by $36$ characters, giving us the number of ways as: $36^6$. Subtracting it with the bad case of the password without atleast one digit : $26^6$ gives us the total number of ways. Hope it helps.

$\endgroup$
1
$\begingroup$

This is the principle of inclusion-exclusion. We see here that it is much easier to count the number of cases without restriction and remove the undesirable cases.

Thus we get

$$(36^6-26^6)+(36^7-26^7)+(36^8-26^8).$$

In each case of a password of length $n$ where $n$ ranges over the integers from $6$ to $8$ inclusive we have removed the case where the password consists only of uppercase letters, leaving us with all possibilities for those passwords which contain at least one digit.

Although this is not always true, the words at least in a problem may imply that the method of inclusion-exclusion is the best way forward. Keep an eye out for similar verbiage in other problems and consider applying the same principle.

$\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.