The Sieve Method in Practice
What you'll learn: How to systematically apply inclusion-exclusion as a filtering "sieve" to count elements that survive multiple constraints.
The Core Idea
The sieve method is inclusion-exclusion viewed as a filtering process. Instead of just computing a formula, you imagine "sieving out" unwanted elements step-by-step, carefully tracking overlaps. It's like filtering coffee: you remove grounds, but must account for what sticks in multiple filter layers.
In practice, you:
- Start with a universe of all candidates
- Define "bad" properties (things you want to exclude)
- Apply inclusion-exclusion to count items with none of the bad properties
This systematizes problems where direct counting is messy.
A Concrete Example
Problem: How many integers from 1 to 100 are not divisible by 2, 3, or 5?
- Universe: 100 integers
- Bad properties: A₂ = divisible by 2, A₃ = divisible by 3, A₅ = divisible by 5
- We want |neither A₂ nor A₃ nor A₅|
Using inclusion-exclusion for "none of the properties":
100 − |A₂ ∪ A₃ ∪ A₅|
= 100 − (|A₂| + |A₃| + |A₅| − |A₂ ∩ A₃| − |A₂ ∩ A₅| − |A₃ ∩ A₅| + |A₂ ∩ A₃ ∩ A₅|)
= 100 − (50 + 33 + 20 − 16 − 10 − 6 + 3)
= 100 − 74 = 26
Notice how we "sieved": removed multiples of 2, 3, 5; added back double-counted overlaps; removed triple-counted ones.
Why "Sieve"?
The name evokes the ancient Sieve of Eratosthenes for primes—crossing out multiples systematically. Here, inclusion-exclusion formalizes that crossing-out with precise overlap correction.
Key Takeaway: The sieve method transforms inclusion-exclusion into a systematic filtering strategy, ideal for "count what remains after excluding overlapping bad properties."