Pigeonhole Principle: my notes on a 3 minute Ma Yuchun video.

She starts with a reference to the principle of inclusion and exclusion which is explained in my notes to another of her videos My FaceBook notes on that video lesson.

She claims that the pigeonhole principle is the simplest and most fundamental principle in combinatorics. I suspect the principle of one-to-one mappings is even more fundamental.

What a wonderful animation of pigeons flying into pigeonholes!

If all pigeons must fit in a pigeonhole and n pigeons fly into n-1 pigeonholes, at least one pigeonhole will have 2 pigeons.

The German mathematician Dirichlet wrote about this principle in 1834 calling it the schubfachprinzip (the drawer principle).

She gives another example: If there are 30 students in a class, then at least two of them are born in the same month.

What are the pigeons and what are the pigeonholes?

In hash tables (which map keys to values), the pigeonhole principle informs us that collisions are inevitable because there are more values than keys or indices.

The quiz she refers to at the end is the following: Given 10 pairs of blue socks and 12 pairs of white socks, how many times do we need to pick a sock at random to guarantee we pick a pair of same color socks?

From the free on-line course: Combinatorial Mathematics with Ma Yuchun of Tsinghua University

Lecture: Week 6, Inclusion-Exclusion Principle and Pigeonhole Principle, Pigeonhole Principle, Pigeonhole Principle