Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Each user on a computer system has a password, which is six 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?

Why am I incorrect in reasoning that the answer is $10*36^5$? If every password must contain a digit, then there are only $10$ ways to choose one character in the password and $36^5$ ways to choose the other 5 characters.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

You’re not taking into account that the digit can occur in any of the six positions. There are $10\cdot36^5$ passwords that begin with a digit. There are also $10\cdot36^5$ passwords that end with a digit; some of these also begin with a digit and have already been counted, but some do not, so your figure of $10\cdot36^5$ is necessarily too small.

The easiest way to count the acceptable passwords is to note that there are $36^6$ six-character strings made up of upper-case letters and digits, and $26^6$ of them are made up entirely of letters, so there are $36^6-26^6$ that include at least one digit.

It is possible to count them directly, but the counting is more complicated. For each of the $6$ positions in the password there are $10\cdot36^5$ passwords having a digit in that position, so to a first approximation there are $6\cdot10\cdot36^5$ acceptable passwords. However, as noted in the first paragraph, this counts some passwords more than once. For each pair of positions in the password there are $10^2\cdot36^4$ passwords having digits in both of those positions, and all of these passwords have been counted twice. Since there are $\binom62$ pairs of positions, we must subtract $\binom62\cdot10^2\cdot36^4$ to get rid of the double-counting. Unfortunately, this overcompensates, and there are further corrections to be made. The net result, given by the inclusion-exclusion principle, is

$$\sum_{k=1}^6(-1)^{k+1}\binom6k10^k36^{6-k}\;.$$

Either way, the result is $1,867,866,560$.

share|improve this answer
    
Why does $36^6-26^6$ represent ones that include at least one digit? I'm sorry, it is just confusing to me. –  user1038665 Oct 27 '12 at 10:16
    
@user1038665: There are $36^6$ altogether. There are $26^6$ that have no digit. $36^6-26^6$ is what’s left after you throw away the ones that have no digit, and those are precisely the ones that have at least one digit. –  Brian M. Scott Oct 27 '12 at 10:21

How many passwords are there, ignoring the "at least one digit" requirement? How many passwords are there with no digits all? Now subtract.


Your answer is incorrect because not only are there 10 ways to choose the digit, but there are 6 places where this digit can go. If you multiplied your answer by 6, it would now be double counting. Example:

  1. Choose the digit 9 to go into position 1, and choose 11119 for the rest of the string.
  2. Choose the digit 9 to go into position 6, and choose 91111 for the first 5 characters.

Answers: $36^6$, $26^6$, $36^6-26^6$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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