1
$\begingroup$

Q: Each user on a computer system has a password, which is six to eight characters long, where each character is an upper-case letter or a digit. Each password must contain at least one digit. How many possible passwords are there?

My approach : $6×36^5×10$ for password of length 6 and so on.

From this question on SO I get that some kind of over counting is happening here and I understand the solution in the book but just can't figure where my approach is wrong.

$\endgroup$
5
$\begingroup$

I'm guessing your reasoning is something like $6$ different 'spots for the digit', $10$ choices for 'the digit', and $36^5$ choices for 'the rest' of the string. But consider that $21ABCD$ will be counted twice by this procedure. Once where 'the digit' is $2,$ the 'spot for the digit' is first, and 'the rest' is $1ABCD,$ and a second time where 'the digit' is $1,$ the 'spot for the digit' is second, and 'the rest' is $2ABCD.$

$\endgroup$
  • $\begingroup$ Ah!! Got it. And this redundancy doesn't happen in $P_6 = 36^6 - 26^6$. The clarity is yet to come in my head but thank you still! $\endgroup$ – momo Dec 16 '17 at 3:43
  • $\begingroup$ And there is no way to remove this redundancy in the method I used? $\endgroup$ – momo Dec 16 '17 at 3:52
  • 1
    $\begingroup$ To do it more along the lines of your approach, it would be best to keep the cases with $1,2,3,4,5,6$ digits separate. For instance there are $$ 10^2\times 26^4\times {6\choose 2}$$ different possibilities with four letters and two digits. So you have $$\sum_{k=1}^6 {6\choose k} 10^k26^{6-k} $$ possibilities. The binomial theorem will help you see that this is equal to the more straightforward $36^6-26^6.$ $\endgroup$ – spaceisdarkgreen Dec 16 '17 at 3:53
  • $\begingroup$ You can't just multiply by an over-counting factor cause different strings are over-counted different amounts (for instance $123456$ is counted six times). $\endgroup$ – spaceisdarkgreen Dec 16 '17 at 3:55
  • $\begingroup$ Awesome! Thank you so much! $\endgroup$ – momo Dec 16 '17 at 3:56

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.