0

I’ve been struggling with this question for a while and was hoping you could help because I think I’ve gone wrong somewhere with my calculations, Firstly I calculated the total number of passwords (including those that didn’t satisfy the criteria) by doing $(26+26+10)^8 = 62^8$ Then I calculated the number of passwords with at least one number: $(10\cdot 62^7)$ (I was thinking the other $7$ characters could be any). I also did the same for at least one uppercase letter: $(26\cdot 62^7)$ and for at least one lowercase letter: $(26\cdot 62^7)$ I then tried to calculate the number of passwords with at least one number and at least one uppercase letter: $(10\cdot 26\cdot 62^6)$, with at least one number and one lowercase letter: $(10\cdot 26\cdot 62^6)$, with at least one uppercase letter and one lowercase letter: $(26\cdot 26\cdot 62^6)$ My logic was to use the inclusion-exclusion rule and find the number of passwords that satisfy all of them: $$62^8 - (10\cdot 62^7) - 2(26\cdot 62^7) + 2(10\cdot 26\cdot 62^6) + (26^2\cdot 62^6) = 6.793308176 \cdot 10^{13}$$ My problem is by the same logic I’ve used, I could simply do $26\cdot 26\cdot 10\cdot 62^5 = 6.193057944 \cdot 10^{12}$ I don’t understand why these two answers are different, have I gone wrong somewhere?

Thank you very much for your help!

Vinyl_cape_jawa
  • 4,794
user649433
  • 1
  • 1
  • 1
  • Look again at some of your values... You claim that $26\cdot 62^7$ is the number of passwords with at least one upper case letter. That is incorrect. Rather, this counts the number of passwords which start with an upper-case letter. As for a hint on how to correct these counts... rather than counting the number of passwords with at least one uppercase letter directly, count how many don't have any uppercase letters at all. – JMoravitz Feb 28 '19 at 20:54
  • Similarly, $26\cdot 26\cdot 10\cdot 62^5$ is also incorrect and counts the number of passwords where the first character is an uppercase letter, the second character is a lowercase letter, the third character is a digit, and the rest are unrestricted, but passwords like "passW07d" should also be counted. – JMoravitz Feb 28 '19 at 20:55
  • 2
    @user The question doesn't need to be an exact replica to be considered duplicate. The idea is the same and the technique to solve it is the same. – Théophile Feb 28 '19 at 21:15
  • Find how many have all digits, all caps, all lower case, only caps and digits, only letters, and only lower case and digits. Subtract the latter three and add back in the first three (look up inclusion-exclusion if you haven't seen this sort of thing before). – Ned Feb 28 '19 at 22:30

1 Answers1

1

As already mentioned in the comments this is an object lesson for applying the inclusion-exclusion principle.

You problem have started already with the wrong calculation of passwords with at least one digit. In fact it is clearly the number of unrestricted passwords minus the number of passwords containing no digits: $$ 62^8-(62-10)^8=62^8-52^8. $$

Similarly the number of passwords containing no uppercase letters is: $$ 62^8-(62-26)^8=62^8-36^8. $$

One could naively assume that we are done if all three false possibilities are subtracted. This however would be wrong. Any set containing only uppercase letters or only lowercase letters or only digits will be subtracted twice. Therefore we should add them back. If there were some additional symbols we should have now subtract all passwords containing only these symbols. As, however, no such symbols are left, the final result is:

$$62^8-52^8-36^8-36^8+26^8+26^8+10^8-0^8=159655911367680.$$

user
  • 26,272