Sign inSign in
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.
as Joe Blitzstein defines itHarvard UniversityThe wording closest to all 9 definitions
Watch it explained

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

8

Each in their own terms, from the easiest level.

  • Vicky Neale

    University of Oxford · Introductory

    If there are more elements in the domain than the codomain, a function cannot be injective.
    • 30:26Functions
    • 52:41Algebra of Sets, De Morgan's Laws, Truth Tables & Cardinality
  • Marten van Dijk

    MIT · Undergraduate

    If more pigeons than holes fly into n holes, at least two pigeons will visit the same hole.
  • Francis Su

    Harvey Mudd College · Undergraduate

    If infinitely many pigeons are placed into finitely many holes, then at least one hole must contain infinitely many pigeons.
    • 50:07Subsequences, Cauchy Sequences
  • Srini Devadas

    MIT · Undergraduate

    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.
    • 49:24Complexity: Approximation Algorithms
  • Christof Paar

    Ruhr University Bochum · Undergraduate

    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

    MIT · Undergraduate

    If a machine with pp states runs for more than pp steps, it must visit at least one state twice.
    • 50:15Regular Pumping Lemma, Conversion of FA to Regular Expressions
  • Ankur Moitra

    MIT · Undergraduate

    If n items are put into m containers, with n > m, then at least one container must contain more than one item.
    • 7:30Pigeonhole Principle

Connections

15

The lectures that define it or assume it, and the concepts next to it.

8 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.