Lesson 2: Inclusion–exclusion for overlapping sets
How many passwords follow the rules?
SkillsInclusion–exclusionMultiplication principleAddition principle
Worked example
A website's passwords are exactly 8 characters long. Each character is one of the 26 lowercase letters or one of the 10 digits, and characters may repeat.
(a) How many passwords are possible with no other rules?
(b) The website now requires at least one digit. How many passwords follow this rule?
(c) It then also requires at least one letter. Use inclusion–exclusion to find how many passwords follow both rules.
(d) An attacker's computer can test passwords per second. How long would it take to test every password allowed in (c)? Comment on what the rules do to security.
Step 1: Count all passwords
Each of the 8 slots has 36 options: .
Step 2: Use the complement for "at least one digit"
Passwords with no digit use letters only, and there are of them. So the number with at least one digit is .
Every password either contains a digit or does not, so (with a digit) = (all) − (no digit).
Step 3: Name the passwords that break a rule
Let be the passwords with no digit, so , and the passwords with no letter, so . A password breaks a rule if it is in .
Step 4: Use inclusion–exclusion
A password in would have no digits and no letters, which is impossible, so and .
Inclusion–exclusion still works when the overlap is empty. It then reduces to the addition principle.
Step 5: Subtract from the total
passwords follow both rules.
Step 6: Find the time
seconds, which is about 4.4 minutes.
Step 7: Evaluate the rules
Each rule removes passwords: together they cut the number of possibilities by about 7.4%, so an attacker testing every password finishes slightly sooner, not later. Rules like these help only by stopping people from choosing common words. Length matters far more: two extra characters multiply the number of passwords by .
Answer
(a) (b) (c) (d) about 261 seconds, or 4.4 minutes. The rules slightly reduce the number of possible passwords; extra length is what makes them much harder to break.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Count everything first.
"At least one" means subtract the outcomes with none.
Two rules means inclusion–exclusion on the outcomes that break them.
Interpret the size of the answer in the context.
Watch out for
Counting "at least one digit" as : that counts passwords with several digits more than once.
Subtracting and and then also subtracting an overlap that does not exist.