ConceptMathematics
Pigeonhole principle
The principle stating that if more than n items are put into n containers, then at least one container must contain more than one item.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Cardinality2Counting2Finite sets2Function2Basic combinatorics1Basic counting1DFA1Generalized pigeonhole principle1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
8Each in their own terms, from the easiest level.
Vicky Neale
If there are more elements in the domain than the codomain, a function cannot be injective.Marten van Dijk
If more pigeons than holes fly into n holes, at least two pigeons will visit the same hole.Francis Su
If infinitely many pigeons are placed into finitely many holes, then at least one hole must contain infinitely many pigeons.Srini Devadas
A combinatorial principle stating that if more items are put into containers than containers exist, at least one container must contain more than one item.Christof Paar
A principle stating that if more items are put into fewer containers than the containers, at least one container must contain more than one item.Michael Sipser
If a machine with states runs for more than steps, it must visit at least one state twice.Ankur Moitra
If n items are put into m containers, with n > m, then at least one container must contain more than one item.
Connections
15The lectures that define it or assume it, and the concepts next to it.