Concept

How does counting the complement simplify an “at least one” condition?

Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk / Chapter 1

"Sometimes we have something difficult to count, but we can turn it around in terms of something much easier. Often this involves counting the complement of something, then subtracting from the total. Suppose a certain website mandated that user passwords be between 6–10 characters in length—every character being an uppercase letter, lowercase letter, digit, or special character (*, #, @, % or &)—but it also required each password to have at least one digit or special character. Without the “at least one digit or special character” part, there are 26 + 26 + 10 + 5 = 67 different choices for each character, so there are 67¹⁰ + 67⁹ + 67⁸ + 67⁷ + 67⁶ = 1,850,456,557,795,600,384 strings. It is easier to count the passwords that don’t satisfy the extra constraint: strings with 6–10 alphabetic-only characters. That is 52¹⁰ + 52⁹ + 52⁸ + 52⁷ + 52⁶ = 147,389,519,403,536,384 illegal passwords. Now subtract: total number of strings − number of illegal passwords = number of legitimate passwords. Therefore, 1,850,456,557,795,600,384 − 147,389,519,403,536,384 = 1,708,735,865,301,022,720 legitimate passwords. The lesson learned is that if counting the elements in some set involves accounting for a lot of different sticky scenarios, it’s worth a try to count the elements not in the set instead, and see if that’s easier."

Related Ideas

How does counting the complement simplify an “at least one” condition? | Stephen Davies, Ph.D. Version 2.2.2 Through Discrete Mathematics A Cool Brisk Walk | Bifalgorithm | Bifalgorithm