The pigeonhole principle and inclusion-exclusion

The pigeonhole principle

If n + 1 pigeons fly into n holes, some hole gets at least two pigeons. Obvious, yet it proves surprising facts:

• Among 13 people, two were born in the same month.
• In any group of 367 people, two share a birthday (366 possible days).
• A drawer holds black and white socks. Take 3 in the dark, and two match.
• A function from a bigger finite set to a smaller one cannot be one-to-one.

The generalized form: if N items go into k boxes, some box holds at least ⌈N/k⌉ items. 100 students in 7 sections: some section has at least ⌈100/7⌉ = 15 students.

The principle says a box like that exists; it does not say which one. Mathematicians call that a non-constructive proof.

The birthday problem

How many people are needed for a 50% chance that two share a birthday? Not 183, but only 23. The chance that n people all have different birthdays is

365/365 × 364/365 × 363/365 × ... × (365 − n + 1)/365

def all_different(n):
    """The chance that n people all have different birthdays (365 equally likely days)."""
    chance = 1.0
    for i in range(n):
        chance *= (365 - i) / 365
    return chance

for n in [10, 22, 23, 30, 50]:
    print(f"{n} people: {1 - all_different(n):.1%} chance of a shared birthday")

The chance passes 50% at 23 people and 97% at 50. The reason: 23 people form C(23, 2) = 253 pairs, and each pair is a chance of a match. The same arithmetic is why a hash function with too few possible outputs has collisions sooner than you expect.

Inclusion-exclusion

For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|. For three:

|A ∪ B ∪ C| = |A| + |B| + |C|
            − |A ∩ B| − |A ∩ C| − |B ∩ C|
            + |A ∩ B ∩ C|

Add the singles, subtract the pairs (counted twice), add back the triple (subtracted once too often).

How many numbers from 1 to 100 are divisible by 2, 3 or 5? Divisible by 2: 50; by 3: 33; by 5: 20; by 6: 16; by 10: 10; by 15: 6; by 30: 3. So 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.

def count(d):
    return 100 // d          # how many of 1..100 are divisible by d

formula = count(2) + count(3) + count(5) - count(6) - count(10) - count(15) + count(30)

brute_force = len([n for n in range(1, 101) if n % 2 == 0 or n % 3 == 0 or n % 5 == 0])
print("inclusion-exclusion:", formula)
print("checking all 100:", brute_force)

Mark lesson complete