1
$\begingroup$

QUESTION: Each user on a computer system has a password, which is six characters long, where each character is an uppercase letter or a digit. Each password must contain at least one digit. How many possible passwords are there? (Modified version of an example Rosen Discrete Maths book)

MY ANSWER: since the password MUST have at least a digit then we can start by picking out this digit first which can be done in $10$ ways and the rest can be digits and letters which will be $36$(i.e $10$ digits + $26$ Uppercase letters) each case.

So the number of possible passwords is $10 \times 36^{5} = 604,661,760$

ANSWER FROM THE BOOK: We have to know all possible passwords $= 36^{6}$ and from this subtract passwords without a digit $26^{6}$
Therefore number of possible passwords = $36^6 - 26^6 = 1,867,866,560$

I understand why the second one is correct but i don't understand how the first one is wrong.

$\endgroup$
2
  • $\begingroup$ You are computing the passwords that have a digit in the first position(see it as a cartesian product if you want $\{1,2,\cdots ,9\}\times \{1,2,\cdots ,9,a,\cdots ,z\}^5$), which is a different thing. $\endgroup$
    – Phicar
    Commented Nov 17, 2023 at 12:31
  • $\begingroup$ As a general guideline: If a problem says you have to have at least $N$ of something (but you could have more) and your solution is to first pick $N$ choices of that thing and then choose the rest of the objects, it's probably wrong. $\endgroup$
    – David K
    Commented Nov 17, 2023 at 14:41

3 Answers 3

1
$\begingroup$

Your solution takes into account only the password that start with a number, the rest could be anything. You should multiply by $6$ to choose the position of that number. $$6\times 10\times36^5 = 3,627,970,560$$ This value is way to high. Why? A lot of password are counted multiple times. Such as

  • choosing 1 as the first character (forced number) then the rest is abcd5 : 1abcd5
  • choosing 5 as the last character (forced number) then the rest is 1abcd : 1abcd5

It will be hard to remove those multiple password since they depend on how many numbers there are.

  • If there are one number in the password, it is counted only once, nothing to do here;
  • If there are two numbers in the password, it is counted twice. How many password have exactly two numbers : ${6\choose2}\times10^2\times26^4=685,464,000$;
  • If there are three numbers in the password, it is counted three times. How many password have exactly three numbers : ${6\choose3}\times10^3\times26^3=351,520,000$;
  • If there are four numbers in the password, it is counted four times. How many password have exactly four numbers : ${6\choose4}\times10^4\times26^2=101,400,000$;
  • If there are five numbers in the password, it is counted five times. How many password have exactly five numbers : ${6\choose5}\times10^5\times26=15,600,000$;
  • If there are six numbers in the password, it is counted six times. How many password have exactly six numbers : ${6\choose6}\times10^6=1,000,000$.

Numbers of different passwords that satisfy your condition: $$\begin{align}3,627,970,560-685,464,000 &-2\times351,520,000-3\times101,400,000\\ &-4\times15,600,000-5\times1,000,000=1,867,866,560\end{align}$$


Since it is a lot of work, it would have been simplier to evaluate how many passwords have 1 number, how many have two, etc. It would give us the same answer. $$\begin{align}{6\choose1}\times10\times26^5 &+{6\choose2}\times10^2\times26^4+{6\choose3}\times10^3\times26^3\\ &+{6\choose4}\times10^4\times26^2+{6\choose5}\times10^5\times26+{6\choose6}\times10^6=1,867,866,560\end{align}$$

$\endgroup$
1
$\begingroup$

I believe that your method would count "5ABCDE" the same as "ABCDE5" but clearly they are different.

$\endgroup$
0
$\begingroup$

If you want to take this approach, you are essentially designating a preferred role to the digit carrying position. In order to fix this, you would need to take 6 copies of what you computed (i.e., where the role of 'digit' position is each of the possible positions) and then apply inclusion-exclusion to remove the arrangements you've counted twice.

To illustrate this, let us think of the much simpler scenario where the passwords have just 2 entries. The correct result needs to be $36^2-26^2=10\cdot 62=620$.

If you do it your way, you have to look at the first position being a digit and the second arbitrary and vice-versa, giving $2\cdot 10\cdot 36=720$ possibilities. However, by doing this, you have counted the passwords that just consist of digits twice. There are $10^2=100$ of those, so the total number of valid passwords would indeed be $720-100=620$.

$\endgroup$

You must log in to answer this question.

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