1

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.

momo
  • 251

1 Answers1

5

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

spaceisdarkgreen
  • 58,508
  • 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! – momo Dec 16 '17 at 03:43
  • And there is no way to remove this redundancy in the method I used? – momo Dec 16 '17 at 03:52
  • 1
    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.$ – spaceisdarkgreen Dec 16 '17 at 03:53
  • 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). – spaceisdarkgreen Dec 16 '17 at 03:55
  • Awesome! Thank you so much! – momo Dec 16 '17 at 03:56