Lesson 2: Inclusion–exclusion for overlapping sets

How many passwords follow the rules?

SkillsInclusion–exclusionMultiplication principleAddition principle

Worked example

  • Complex unfamiliar
  • Technology active

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 101010^{10} passwords per second. How long would it take to test every password allowed in (c)? Comment on what the rules do to security.

1 of 7 steps
  1. Step 1: Count all passwords

    Each of the 8 slots has 36 options: 368=2 821 109 907 456≈2.821×101236^8 = 2\,821\,109\,907\,456 \approx 2.821 \times 10^{12}.

    368≈2.821×101236^8 \approx 2.821 \times 10^{12}

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Count everything first.

  2. "At least one" means subtract the outcomes with none.

  3. Two rules means inclusion–exclusion on the outcomes that break them.

  4. Interpret the size of the answer in the context.

Watch out for

  • Counting "at least one digit" as 10×36710 \times 36^7: that counts passwords with several digits more than once.

  • Subtracting 26826^8 and 10810^8 and then also subtracting an overlap that does not exist.

Save your progress with a free account