2
$\begingroup$

I am working on a homework problem where I need to find the total number of passwords that have exactly 8 characters.

Constraints:

  • each character is either an uppercase letter (A..Z) or a digit (0..9)
  • each password must contain at least 2 digits

Here is what I have so far:

I know that each there are 8 characters in each password so the total number of passwords should be the product of the number of choices for each of the 8 slots, barring the constraints.

So for 6 of the slots I have 36 options, 26 letters and 10 digits, and for the other two slots I can only choose digits, since the constraints state that I must have at least 2 digits; this leaves me with this:

$36^6 \times 10 \times 10 = 217\, 678\, 233\, 600$

This gives me over 200 billion passwords(which seems really large), is there anyway that I can use the C(n,r) formula to verify this result?

Any help would be appreciated.

EDIT: New Solution

Taking your advice I computed the total number of passwords $P_t$ you could have with 8 characters, them computed the total with $i$ digits in any position in the password where $1 \leq i \leq 8$

$P_t = 36^8 = 2,821,109,907,456$

Let $Q_i$ be the total number of passwords with $i$ digits that appear anywhere in the string:

$Q_0 = C(8,0) * 10^0 * 26^8 = \text{208,827,064,576}$ $Q_1 = C(8,1) * 10^1 * 26^7 = \text{642,544,814,080}$ $Q_2 = C(8,2) * 10^2 * 26^6 = \text{864,964,172,800}$ $Q_3 = C(8,3) * 10^3 * 26^5 = \text{665,357,056,000}$ $Q_4 = C(8,4) * 10^4 * 26^4 = \text{319,883,200,000}$ $Q_5 = C(8,5) * 10^5 * 26^3 = \text{98,425,600,000}$ $Q_6 = C(8,6) * 10^6 * 26^2 = \text{18,928,000,000}$ $Q_7 = C(8,7) * 10^7 * 26^1 = \text{2,080,000,000}$ $Q_8 = C(8,8) * 10^8 * 26^0 = \text{100,000,000}$

Now since I am only looking for passwords where there are at least 2 digits, only $Q_1$ is invalid since it does not have at least 2 digits. So the total number of passwords with at least 2 digits is $\sum_{i=2}^{8} Q_i$ or just $(P_t - Q_1 - Q_0)$

$\sum_{i=2}^{8} Q_i = Q_2 + Q_3 + Q_4 + Q_5 + Q_6 + Q_7 + Q_8 = 1,969,738,028,800$

or

$\begin{align*} P_t - Q_1 - Q_0 &= 2,821,109,907,456 - 642,544,814,080 - 208,827,064,576\\ &= 1,969,738,028,800 \end{align*}$

  • 0
    @ArturoMagidin I didn't recognize the relationship you were trying to point until I had written all of the equations out. It's just easier for me to see relationships when I generalize the formula, in this case $Q_i = C(n,r) * 10^r * 26^{n-r}$2012-03-19

2 Answers 2

2

The number may seem high, but it's actually too low. Just as a hint: You certainly have counted the password abcdef12. But did you count 12abcdefg?

  • 0
    I think Arturo's comment to your revised version sums it up - it's correct, but a bit unnecessary extra work; you had $P_t$ already and only needed $Q_0$ and $Q_1$.2012-03-19
1

Hint: It is easier to count all the $8$ character passwords and subtract the ones that don't have two digits-how many total $8$ character strings are there? How many are there with no digits? For the $1$ digit ones, you have how many ways to choose where the digit goes?