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*}$$

$\endgroup$
6
  • $\begingroup$ Why do you want to verify this using $\binom{n}{r} $? $\endgroup$
    – Quixotic
    Mar 19, 2012 at 4:15
  • $\begingroup$ @Foool I don't know if the answer is right, and am looking for a way to verify it. $\endgroup$
    – Hunter McMillen
    Mar 19, 2012 at 4:20
  • 1
    $\begingroup$ You never count in how many ways you are selecting which slots will be forced to have numbers in them; so you are only counting the number of passwords in which a specific two slots have numbers (say, last and penultimate slots). If you add a factor to account for that, you will end up overcounting. My suggestion: count the total number without restrictions, count the number of passwords with exactly one number and 7 letters; and count the number of passwords with all letters. $\endgroup$
    – Arturo Magidin
    Mar 19, 2012 at 4:25
  • $\begingroup$ @ArturoMagidin I have revised my answer, please review it when you have time. $\endgroup$
    – Hunter McMillen
    Mar 19, 2012 at 15:20
  • $\begingroup$ @Hunter: I think you are doing overkill (unless there are other questions later involving other totals). You really only need to compute $P_t$, $Q_0$, and $Q_1$ in order to find the total you are looking for. Otherwise, it looks fine. $\endgroup$
    – Arturo Magidin
    Mar 19, 2012 at 15:22

2 Answers 2

Reset to default
2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I have revised my answer, please review it when you have time. $\endgroup$
    – Hunter McMillen
    Mar 19, 2012 at 15:20
  • $\begingroup$ 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$. $\endgroup$
    – Desiato
    Mar 19, 2012 at 17:21
1
$\begingroup$

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?

$\endgroup$
0

You must log in to answer this question.

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