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$ 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$ Mar 19, 2012 at 4:25
  • $\begingroup$ @ArturoMagidin I have revised my answer, please review it when you have time. $\endgroup$ 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$ Mar 19, 2012 at 15:22

2 Answers 2

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

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.