Discrete mathematics problem - Probability theory and counting [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

开发者_如何学运维

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question

I'm taking a discrete mathematics course, and I encountered a question and I need your help. I don't know if this is the right place for that though :)

It says:

Each user on a computer system has a password, which is six to eight 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?

The book solves this by adding the probabilities of having six,seven and eight characters long password. However, when he solves for probability of six characters he does this

P6 = 366 - 266

and does

P7 = 367 - 267

and

P8 = 368 - 268

and then add them all.

I understand the solution, but my question is why doesn't calculating, P6 = 10*36⁵ and the same for P7 and P8, work? 10 for the digit and 36 for the alphanumeric?

Also, if anyone could give me another solution, other than the one in the book.

Thank you very much :)

---

You're forgetting that the number can be in any position.

---

I understand the solution, but my question is why doesn't calculating, P6 = 10*36^5 and the same for P7 and P8, work? 10 for the digit and 36 for the alphanumeric?

you're guaranteeing that there is a digit by using the 10,
but, there's nothing to stop there from being a digit in the other positions (36 choices)
that's why you have to get all the combs in which there are digits and subtract all the ones where there aren't
which leads to P6 = 36^6 - 26^6

If I think if an alternate solution I'll revisit this post, but for now I don't see why you wouldn't be satisfied with the provided one, knowing why yours doesn't work

---

If you do it like 36^5 * 10, that means "take the first five positions and put some random letters/digits there and fill the sixth (and only the sixth) position with a digit" - but your digit can be in each place.

Consider the following: If you set 5 places with letters/digits, then putting a digit in the sixth place yields 10 possibilities (the sixth position can then hold every number from 0 to 9), and if you put the digit in front of the letters, this would yield another 10 possibilities (then, the first place could contain every digit from 0 to 9), so by multipliing by 10 you forget some possibilities.

If you want to calculate it "the raw way", you could do the following (I do it with six places, you can adapt it to 7 or 8). Since a password must contain at least one digit, it can hold 1, 2, 3, 4, 5 or 6 digits, resp 5, 4, 3, 2, 1 or 0 letters.

If you have k digits in 6 places in total, there are 6 over k possibilities to choose these k places. Each of these k places can be filled with a digit, so you have 10^k possibilities for the digits and 26^(6-k) possibilities for letters.

So, for k digits, you have 10^k * 26^(6-k) possibilities. Thus, since you can distribute the k digits in 6 over k ways, you have

sum(k from 1 to 5: (6 over k) * 10^k * 26^(6-k)) = 36^6-26^6

possibilities in total.