Lecture 1: Pigeonhole Principle

Lecture 1: Pigeonhole Principle

by Ankur Moitra

Formal & Physical Sciences Mathematics PBMathematicsPBVCombinatorics and graph theory
🎙 Ankur Moitra 👥 6.4M 📅 December 17, 2025 ⏱ 73 min 👁 50K 📄 lecture 🧭 2026-08-06
Available in: English (current) Français

Keywords

pigeonhole principleproof by contradictiongraph theorydegreeparty lemma

Summary

This is the first lecture of MIT’s 18.200 course, Principles of Discrete Applied Mathematics, taught by Ankur Moitra. The lecture begins with course logistics, including the communication-intensive nature of the class and the importance of writing clear proofs. The main mathematical content introduces the pigeonhole principle, a simple yet powerful combinatorial tool. The principle states that if n items are placed into m containers and n > m, then at least one container must contain more than one item. The instructor proves this using a proof by contradiction, emphasizing the importance of clearly stating the proof technique. He then illustrates the principle with the classic example of picking socks to guarantee a pair. The lecture also covers a generalization of the principle: if n items are placed into m containers, at least one container has at least ceil(n/m) items. To demonstrate the principle’s power, the instructor introduces a lemma about parties: in any group of n people, there are at least two people who know the same number of other people. He shows how to model this problem using graph theory, where people are nodes and edges represent acquaintance. The degree of a node is the number of edges incident to it. The proof uses the pigeonhole principle by considering the possible degrees of nodes, which range from 0 to n-1, but cannot include both 0 and n-1 simultaneously. Thus, there are at most n-1 possible degrees for n nodes, guaranteeing a collision. The lecture concludes with a brief introduction to probability and sample spaces, setting the stage for future topics.

261 words

Critical Evaluation

This lecture provides a solid introduction to the pigeonhole principle, a fundamental concept in combinatorics and discrete mathematics. The instructor, Ankur Moitra, is a well-known computer scientist and professor at MIT, lending credibility to the content. The presentation is clear and well-structured, beginning with a simple example (socks) to build intuition, then formalizing the principle and proving it via contradiction. The proof is rigorous and follows the guidelines for good proof-writing that the instructor emphasizes, such as clearly stating the proof technique and providing a blueprint for the argument. The lecture also demonstrates the power of the principle through a non-obvious application: the party lemma, which is elegantly solved by modeling the problem as a graph and applying the pigeonhole principle to the degrees of nodes. This example effectively illustrates the importance of abstraction and finding the right representation in mathematical problem-solving. The instructor’s teaching style is engaging, with occasional humor and interactive elements, such as asking the audience for input. The content is appropriate for an undergraduate-level course in discrete mathematics, and the level of technical detail is suitable for students with some mathematical maturity. The lecture is part of MIT OpenCourseWare, a reputable source for high-quality educational content. The video description includes links to the course page and other resources, which are useful for further study. Overall, this is an excellent lecture that effectively introduces a key concept and demonstrates its applications, making it a valuable resource for students and enthusiasts of mathematics.

245 words

Title / Content Match

The title accurately reflects the content, which focuses on the pigeonhole principle and its applications.

Quality & Reliability

9/10

Lecture by MIT professor Ankur Moitra, part of MIT OpenCourseWare, a reputable academic source. The content is mathematically rigorous, with clear proofs and examples. The instructor is an established expert in the field.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

  • Pigeonhole Principle - Wikipedia — Provides a comprehensive explanation of the principle and its many applications, consistent with the lecture's content.
  • MIT OpenCourseWare — The platform hosting this lecture, known for high-quality educational content.

Contribution & Novelties

This lecture provides a clear and engaging introduction to the pigeonhole principle, a fundamental concept in combinatorics. The instructor emphasizes the importance of proof-writing and abstraction, using the principle to illustrate these skills. The lecture is part of MIT’s OpenCourseWare, making high-quality educational content freely accessible.

Pour aller plus loin :

106 words

Radar Profile

The radar chart shows high scores in quality of information, technical level, and reliability, with a slightly lower score in quantity of information due to the lecture's focused scope. This indicates a well-balanced, rigorous educational resource.

Reliability 9/10