Search code examples
complexity-theorycounting

Counting and Complexity for Password Possibility


Each password should contain exactly 8 alphanumeric characters (0-9, a-z). The first and the last character of each password should be a number. The password must contain the 3-character string “TCO”. Explain how many unique passwords can be created?


Solution

  • There are 8 positions that can be filled with alphanumeric characters. I will assume that lowercase and uppercase letters are both available, but the analysis is quite similar if only lowercase letters are allowed.

    First, we know the first and eighth symbols are decimal digits. These can both be chosen independently from all ten decimal digits. There are 100 ways to choose two decimal digits (00, 01, …, 99).

    Second, we must place the fixed string TCO somewhere in the remaining 6 symbols. There are precisely four ways to do this: we can start the substring TCO at position two, three, four or five.

    Finally, we have three vacant spots that can be filled with any of the available symbols. Because we are allowing lowercase and uppercase letters from the English alphabet as well as the decimal digits, there are 62 possibilities in total (26 lowercase letters, 26 uppercase letters and ten decimal digits). Each of the vacant spots can be chosen independently so we find 26^3 = 17576 total ways in which this can be done.

    Because each of these choices happens independently, the total number of ways to make all three choices is the product of the number of ways in which each choice can be made: 100 x 4 x 17576 = 7030400.