MIT OpenCourseWare · YouTube · 4:13
This introductory discrete-mathematics clip presents the pigeonhole principle first informally and then as the contrapositive of a mapping rule about total injections. The visual proof uses 5 pigeons and 4 holes, followed by the formal statement “total injection from A to B implies |A| ≤ |B|” and its contrapositive “If |A| > |B|, then no total injection from A to B.” The speaker then applies the idea to a 5-card draw, treating the 5 cards as pigeons and the 4 suits as pigeonholes, concluding that at least two cards must have the same suit. This 120-second lecture segment introduces the pigeonhole principle through card examples and then states the generalized form. First, 5 cards assigned to 4 suits force at least two cards to share a suit. Next, the speaker generalizes to 10 cards and 4 suits, arguing by contradiction that fewer than 3 cards in every suit would allow at most 8 cards total, so some suit must contain at least 3 cards. The notation is explained as rounding up the average load. The segment ends with the general theorem: if n pigeons are assigned to h holes, then some hole contains at least pigeons. This short video clip introduces the Generalized Pigeonhole Principle. A slide displays the formal definition: if there are n pigeons and h holes, then some hole must contain at least the ceiling of pigeons. The speaker explains this verbally as the average number of pigeons per hole.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The clip opens on a lecture title slide for “The Pigeonhole Principle” in Mathematics for Computer Science, while the speaker introduces it as a counting principle so obvious that it may already be used without notice.
The first mathematical statement is the informal pigeonhole principle: if there are more pigeons than pigeonholes, then some hole must contain at least two pigeons. The slide builds this sentence visually, first showing 5 pigeon images and then 4 green U-shaped holes.
The animation makes the counting idea concrete by moving the 5 pigeons into the 4 holes. Because there are more pigeons than holes, at least one hole ends up with 2 pigeons, matching the displayed conclusion “have ≥ two pigeons!”
The presentation then translates the informal picture into set language. The slide states the mapping rule: a total injection from A to B implies |A| ≤ |B|. Here A is the source set, B is the target set, and |A| and |B| denote their sizes.
The speaker obtains the pigeonhole principle by taking the contrapositive of the mapping rule. The highlighted statement becomes: if |A| > |B|, then no total injection from A to B is possible. This is the formal version of “more pigeons than pigeonholes.”
The speaker explains the injection language with arrows. A total injection would require an arrow leaving every element of A and at most one arrow entering each element of B. If A has more elements than B, forcing every element of A to send out an arrow makes two arrows enter the same element of B, just as two pigeons enter the same hole.
The lecture briefly mentions that more elaborate applications exist in the text, including examples about people in the Boston area with the same number of head hairs and subsets of numbers with the same sum, but these are not developed in this clip.
The worked application is a 5-card draw. The claim is that any set of 5 cards must contain at least 2 cards with the same suit. The slide states this directly as “must have ≥ 2 with the same suit.”
The final visual model identifies the pigeons and holes for the card example: the 5 cards are the pigeons, and the 4 suits—spades, hearts, diamonds, and clubs—are the holes. Since , the pigeonhole principle implies that at least one suit must receive at least two cards.
The segment opens with a concrete counting model: 5 cards are treated as “pigeons” and 4 suits as “holes.” The visual layout places five card placeholders above four suit containers, making the assignment problem explicit.
Because there are more cards than suits, the lecturer argues that any assignment must crowd at least two cards into the same suit. This is the simplest form of the pigeonhole idea: if objects outnumber boxes, some box receives at least two objects.
The lecture then shifts to a slightly harder case: 10 cards and 4 suits. The central question becomes how many same-suit cards are guaranteed no matter how the 10 cards are distributed.
To answer this, the speaker tests the opposite possibility: could every suit contain fewer than 3 cards? Since card counts are integers, that would mean at most 2 cards per suit.
Multiplying the maximum per-suit count by the number of suits gives at most 8 cards total. But the premise says there are 10 cards, so the assumption fails. Therefore at least one suit must contain 3 or more cards.
The same conclusion is then compressed into formula form on the slide: the guaranteed number of same-suit cards is at least . The lecturer explains that is the average load per suit, and not all suits can stay below average.
Because the actual number of cards in a suit must be an integer, the average is rounded up. The speaker explicitly defines the corner brackets as the ceiling operation, meaning “round up to the nearest integer.”
Finally, the concrete card example is abstracted into the Generalized Pigeonhole Principle: if n pigeons are assigned to h holes, then some hole contains at least pigeons. The closing interpretation is that is the average number per hole, and the ceiling converts that average into a valid integer lower bound.
The video presents the Generalized Pigeonhole Principle. The slide shows the formula: If n pigeons and h holes, then some hole has >= pigeons. The speaker explains that this means at least one hole must have a number of pigeons greater than or equal to the average number of pigeons per hole.
The video states the simple counting principle: if there are more pigeons than pigeonholes, then at least one pigeonhole contains two or more pigeons. The animation uses 5 pigeons and 4 holes to show that distributing the pigeons forces one hole to hold 2 pigeons.
The informal principle is connected to a formal mapping rule. If there is a total injection from set A to set B, then the size of A is less than or equal to the size of B. The symbols |A| and |B| denote cardinalities.
Taking the contrapositive of the mapping rule gives the formal pigeonhole statement used in the clip: if |A| > |B|, then no total injection from A to B exists. This matches the idea that more pigeons than holes prevent a one-to-one placement.
The speaker describes a total injection as an arrow diagram in which every element of A has an outgoing arrow and each element of B receives at most one incoming arrow. When |A| > |B|, giving every element of A an outgoing arrow forces two arrows to enter the same element of B.
The clip applies the pigeonhole principle to playing cards. A set of 5 cards must contain at least 2 cards with the same suit because the 5 cards are distributed among only 4 suits.
The visual model labels the 5 cards as pigeons and the 4 suits as holes. The suit symbols shown are spades, hearts, clubs, and diamonds. This makes the card example a direct instance of the earlier 5-pigeons-4-holes animation.
This card records the opening example. Five cards are assigned to four suits, so at least one suit must contain at least two cards. The visual mapping from card placeholders to suit containers makes the counting argument concrete.
For 10 cards distributed among 4 suits, the lecturer proves that some suit must contain at least 3 cards. The key contradiction is that fewer than 3 in every suit would allow at most 8 cards total, which is impossible when there are 10 cards.
The notation means to round x up to the nearest integer. In this lesson it turns the average load into the integer lower bound 3, and later turns into the general bound.
When n objects are assigned to h boxes, at least one box contains at least objects. The speaker motivates this by interpreting as the average number per box and then rounding up because box counts are integers.
States that if n items are put into m containers, then at least one container must hold at least items. In the context of the video, 'pigeons' are items and 'holes' are containers.
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
Slide text uses A in “total injection from A to B implies |A| ≤ |B|” and “no total injection from A to B.”
Speaker says “from a set A to a set B.”
A
Source set in the mapping rule; informally corresponds to the set of pigeons.
Finite set; exact finiteness assumption is not stated on the slide.
Slide text uses B in “total injection from A to B implies |A| ≤ |B|” and “no total injection from A to B.”
Speaker says “from a set A to a set B.”
B
Target set in the mapping rule; informally corresponds to the set of pigeonholes.
Finite set; exact finiteness assumption is not stated on the slide.
Slide shows |A| in |A| ≤ |B| and |A| > |B|.
Speaker says “the size of A.”
|A|
Cardinality or size of set A.
Nonnegative integer for finite sets; video does not explicitly state the domain.
Slide shows |B| in |A| ≤ |B| and |A| > |B|.
Speaker says “the size of B.”
|B|
Cardinality or size of set B.
Nonnegative integer for finite sets; video does not explicitly state the domain.
Slide displays |A| ≤ |B|.
Speaker says “less than or equal to.”
≤
Less than or equal to relation between cardinalities.
Order relation on numbers/cardinalities.
Slide displays |A| > |B|.
Speaker says “greater than.”
>
Strictly greater than relation between cardinalities.
Order relation on numbers/cardinalities.
Slide displays “have ≥ two pigeons!”
Speaker says “at least two pigeons.”
≥ two
At least two, used for the number of pigeons in one hole.
Counting statement about a pigeonhole occupancy.
Slide displays “must have ≥ 2 with the same suit.”
Speaker says “at least two cards with the same suit.”
≥ 2
At least two cards, used in the card-draw conclusion.
Counting statement about cards sharing a suit.
The speaker says, "If you have five cards, there's more pigeons, cards, than suits, holes".
Slide title reads "5 Card Draw"; text labels "5 cards (pigeons)" and "4 suits (holes)".
5 cards
Number of objects being assigned to categories in the first example.
positive integer count of cards
The speaker refers to "suits, holes" while discussing assigning cards to suits.
Four blue U-shaped containers are shown with suit symbols beneath them.
4 suits
Number of categories or boxes into which the cards are assigned.
positive integer count of categories
The speaker says, "Suppose I have ten cards" and later discusses distributing ten cards into four slots.
Slide title reads "10 Card Draw"; formula shows numerator 10.
10 cards
Number of objects in the generalized card example.
positive integer count of cards
The speaker says, "if I have n pigeons".
Slide text reads "If n pigeons and h holes".
n
General number of pigeons or objects being distributed.
positive integer count of objects
Speaker introduces the pigeonhole principle as a counting principle and states the simple form.
Slide text reads “If more pigeons than pigeonholes,” then “then some hole must have ≥ two pigeons!”
Five pigeon images appear above four green U-shaped holes, then the pigeons move into the holes so that one hole contains two pigeons.
The video presents the pigeonhole principle as an obvious counting principle: if there are more pigeons than pigeonholes, then at least one pigeonhole must contain two or more pigeons. The visual example uses five pigeons and four holes.
There are more pigeons than pigeonholes.
The conclusion concerns at least one hole containing ≥ two pigeons.
Speaker says this is an informal way of saying something formally seen already among the mapping rules.
Slide text reads “Mapping Rule: total injection from A to B implies |A| ≤ |B|.”
The slide does not explicitly state that A and B are finite, although the surrounding lecture context and cardinality comparison suggest finite sets.
The formal mapping rule shown on the slide says that a total injection from set A to set B implies that the cardinality of A is less than or equal to the cardinality of B. The speaker frames the pigeonhole principle as an informal version of this rule.
There is a total injection from A to B.
A and B are treated as sets whose sizes can be compared.
Speaker says “taking the contrapositive of that” and explains that if |A| > |B|, no total injection from A to B is possible.
Slide text inside a dashed box reads “If |A| > |B|, then no total injection from A to B.”
By taking the contrapositive of the mapping rule, the video obtains the formal pigeonhole statement: if the size of A is greater than the size of B, then there cannot be a total injection from A to B. The speaker interprets this as forcing at least two arrows, or pigeons, to land in the same target element, or pigeonhole.
Assumes the mapping rule total injection from A to B implies |A| ≤ |B|.
Uses contrapositive reasoning.
A and B are compared by cardinality.
Speaker explains “No total injection means that there’s no relation that has an arrow out of everything in A and at most one arrow into B.”
Speaker continues that if everything in A has an arrow out of it, there have to be at least two arrows, two pigeons, coming to the same pigeonhole in B.
The video gives an arrow-based intuitive explanation rather than a fully formal definition of total function and injective function.
The speaker describes a total injection using arrows: every element of A must have an arrow leaving it, and each element of B may receive at most one arrow. If |A| > |B|, assigning an outgoing arrow to every element of A forces two arrows to enter the same element of B, matching the pigeonhole picture.
Arrows represent a relation or mapping from A to B.
Totality requires an arrow out of every element of A.
Injectivity requires at most one arrow into each element of B.
Speaker says the modest application is: if I have a set of five cards, then I have to have at least two cards with the same suit.
Slide text reads “example: 5 Card Draw”, “set of 5 cards:”, and “must have ≥ 2 with the same suit.”
Later slide labels “5 cards (pigeons)” and “4 suits (holes)” with four suit symbols under four blue holes.
The audio cuts off after “and if,” so any completed formal proof sentence for the card example is not present in this clip.
The video applies the pigeonhole principle to a set of five playing cards. The five cards are treated as pigeons and the four suits—spades, hearts, diamonds, clubs—as pigeonholes. Since , at least two cards must share the same suit.
The collection contains 5 cards.
The relevant classification has 4 suits.
Cards are assigned to their suit.
Speaker explains that with five cards and four suits, assigning each card to a suit forces at least two cards into the same suit.
Five card placeholders are mapped by arrows to four suit containers.
This segment models cards as pigeons and suits as holes. Because there are more cards than suits, any assignment of each card to one suit must place at least two cards in the same suit. The visual mapping makes the counting argument concrete.
Each of the 5 cards is assigned to exactly one of the 4 suits.
The conclusion is a guaranteed lower bound, not a statement about a specific random draw.
Speaker asks how many cards of the same suit are guaranteed among 10 cards and argues that fewer than 3 in every hole would allow at most 8 cards total.
Slide shows "10 Card Draw", then "< 3 cards in every hole?", then the formula .
For 10 cards distributed among 4 suits, the speaker derives a guaranteed minimum of 3 cards sharing a suit. The reasoning is that if every suit had fewer than 3 cards, then each suit would have at most 2 cards, giving at most 8 cards total, which contradicts having 10. Equivalently, the average load is , so some suit must reach at least the next integer above that average.
There are 10 cards in total.
There are 4 suits available as categories.
Each card belongs to exactly one suit.
The result is a guaranteed lower bound over all possible distributions.
Speaker says, "these corner braces mean round up to the nearest integer".
Annotation points to the ceiling brackets around .
The notation means to round x up to the nearest integer. In this lesson it converts the average number of cards per suit, , into the integer lower bound 3.
x is a real number.
In this video x is a ratio such as or .
Speaker states the general rule: if there are n pigeons and h holes, then some hole has at least rounded up.
Slide title reads "Generalized Pigeonhole Principle" and displays the formula.
When n objects are assigned to h boxes, at least one box contains at least objects. The speaker interprets as the average number of pigeons per hole, then rounds up because the actual count in a hole must be an integer.
n and h are positive integers.
Each pigeon is assigned to exactly one hole.
The conclusion asserts existence of at least one hole meeting the bound.
Slide displays the text 'Generalized Pigeonhole Principle' and the formula 'If n pigeons and h holes, then some hole has >= pigeons.'
Speaker states: 'the pigeonhole principle can be formulated as saying at least one hole has to have greater than or equal to the average number. And that is the generalized pigeonhole principle.'
The Generalized Pigeonhole Principle states that if there are n pigeons and h holes, then at least one hole must contain a number of pigeons greater than or equal to the ceiling of the average number of pigeons per hole ().
n and h are positive integers
Speaker states the simple form of the pigeonhole principle.
Slide text states “If more pigeons than pigeonholes, then some hole must have ≥ two pigeons!”
If there are more pigeons than pigeonholes, then some pigeonhole must contain at least two pigeons.
There are more pigeons than pigeonholes.
Existential conclusion: some hole has ≥ two pigeons.
Speaker identifies this as one of the mapping rules.
Slide text reads “Mapping Rule: total injection from A to B implies |A| ≤ |B|.”
The video does not explicitly state whether A and B must be finite, though the use of size comparison suggests finite sets.
If there is a total injection from A to B, then |A| ≤ |B|.
There is a total injection from A to B.
A and B are sets with comparable cardinalities.
Universal over sets A and B satisfying the hypothesis.
Speaker says “taking the contrapositive of that” and states the resulting condition.
Slide text reads “If |A| > |B|, then no total injection from A to B.”
If |A| > |B|, then no total injection from A to B is possible.
|A| > |B|.
Universal over sets A and B with |A| > |B|.
Speaker states that a set of five cards must have at least two cards with the same suit.
Slide text reads “set of 5 cards: must have ≥ 2 with the same suit.”
Slide labels 5 cards as pigeons and 4 suits as holes.
The clip ends before the speaker completes the explanatory sentence after “and if.”
Any set of 5 playing cards must contain at least two cards with the same suit.
The set contains 5 cards.
Cards are classified into 4 suits.
Universal over sets of 5 cards; existential conclusion that some suit occurs at least twice.
Speaker concludes, "at least two pigeons in the same hole, at least two cards of the same suit, maybe more".
Arrows show multiple cards directed toward the same suit container.
If 5 cards are assigned to 4 suits, then at least one suit contains at least 2 cards.
There are 5 cards.
There are 4 suits.
Each card is assigned to exactly one suit.
For every assignment of the 5 cards to the 4 suits, there exists a suit containing at least 2 cards.
Speaker says, "I have to bunch them up and have at least three cards of the same suit".
Formula states .
If 10 cards are assigned to 4 suits, then at least one suit contains at least 3 cards.
There are 10 cards.
There are 4 suits.
Each card is assigned to exactly one suit.
For every assignment of the 10 cards to the 4 suits, there exists a suit containing at least 3 cards.
Speaker states the general theorem in words.
Slide displays the generalized formula.
If n pigeons are assigned to h holes, then some hole contains at least pigeons.
n is a positive integer.
h is a positive integer.
Each pigeon is assigned to exactly one hole.
For every assignment of n pigeons to h holes, there exists a hole containing at least pigeons.
Speaker starts from the mapping rule and says “taking the contrapositive of that.”
Slide shows both “total injection from A to B implies |A| ≤ |B|” and “If |A| > |B|, then no total injection from A to B.”
Begin with the mapping rule displayed on the slide.
Observed slide formula and speaker’s statement of the mapping rule.
Take the contrapositive to obtain the formal pigeonhole statement used in the video.
Speaker explicitly says “taking the contrapositive of that”; the slide displays the contrapositive in a dashed box.
Interpret the failure of a total injection in arrow language: if all elements of A must map out while B has fewer elements, two arrows must enter the same element of B.
Speaker explains no total injection as no relation with an arrow out of everything in A and at most one arrow into B, then says there have to be at least two arrows to the same pigeonhole in B.
The informal pigeonhole principle is presented as the contrapositive of the mapping rule for total injections.
Speaker asks “Why?” and answers that there are four suits: spades, hearts, diamonds, clubs.
Slide states “set of 5 cards: must have ≥ 2 with the same suit.”
Slide labels “5 cards (pigeons)” and “4 suits (holes).”
The final spoken clause is cut off after “and if,” so the clip does not contain a fully spoken concluding sentence for this derivation.
Identify the objects being distributed as the five cards.
Slide labels “5 cards (pigeons)” and speaker says “if I have a set of five cards.”
Identify the categories as the four suits: spades, hearts, diamonds, clubs.
Speaker names the four suits; slide labels “4 suits (holes)” and shows four suit symbols.
Compare the number of cards with the number of suits.
This is the numerical instance of “more pigeons than pigeonholes.”
Conclude that some suit must contain at least two of the five cards.
Follows from the pigeonhole principle stated earlier in the clip.
A set of five cards must contain at least two cards with the same suit because five cards are placed into four suit categories.
Speaker reasons by contradiction from "less than three cards in every hole" to "at most eight elements" and then to the need for at least three in one hole.
Slide shows the question "< 3 cards in every hole?" followed by the formula .
Assume, for contradiction, that every suit contains fewer than 3 cards.
This is the hypothesis tested explicitly by the speaker.
Since card counts are integers, fewer than 3 in each suit means at most 2 in each suit.
Integer-valued counts make "< 3" equivalent to "".
With 4 suits and at most 2 cards per suit, the total number of cards would be at most 8.
Multiplying the maximum per-hole count by the number of holes gives the maximum total under the assumption.
But there are actually 10 cards, contradicting the assumption that all suits could have fewer than 3.
The assumed upper bound 8 is less than the given total 10.
Therefore some suit must contain at least 3 cards; equivalently, the average is rounded up to the integer lower bound 3.
The speaker identifies as the average number per hole and applies the ceiling function because the final count must be an integer.
Among any 10 cards assigned to 4 suits, at least one suit contains at least 3 cards.
Speaker says can be understood as the average number of pigeons per hole and then rounds up.
Slide displays as the general bound.
Distribute n pigeons among h holes.
This is the setup stated on the slide and in the narration.
Compute the average number of pigeons per hole.
The speaker explicitly interprets as the average load per hole.
Not all holes can be below this average, so at least one hole must have a count reaching or exceeding it.
This is the averaging intuition used by the speaker.
Because hole counts are integers, the guaranteed lower bound is the ceiling of the average.
The speaker states that the corner braces mean round up to the nearest integer.
Some hole contains at least pigeons.
Speaker calls it a much more modest application of the pigeonholing principle and states the five-card claim.
Slide title reads “example: 5 Card Draw” and text reads “set of 5 cards: must have ≥ 2 with the same suit.”
Slide shows five card placeholders labeled as pigeons and four suit holes labeled spade, heart, club, diamond.
The clip ends before the speaker completes the final explanatory phrase after “and if.”
Show that any set of 5 playing cards must contain at least two cards with the same suit.
There is a set of 5 cards.
There are 4 suits: spades, hearts, diamonds, clubs.
Each card belongs to exactly one suit.
Prove that at least two cards share the same suit.
Treat the cards as the items being placed into categories.
Slide explicitly labels “5 cards (pigeons).”
Treat the suits as the pigeonholes.
Slide explicitly labels “4 suits (holes)” and shows four suit symbols.
There are more cards than suits.
Numerical comparison from the given counts.
By the pigeonhole principle, at least one category must receive two or more cards.
Applies the informal pigeonhole principle stated earlier in the clip.
At least two of the five cards have the same suit.
The slide’s visual model places 5 card pigeons into 4 suit holes, making the conclusion a direct instance of “more pigeons than pigeonholes.”
Speaker introduces the case of five cards and four suits.
Slide title is "5 Card Draw" with labels "5 cards (pigeons)" and "4 suits (holes)".
Given 5 cards and 4 suits, what can be guaranteed about cards sharing a suit?
There are 5 cards.
There are 4 suits.
Each card is assigned to one suit.
Find a guaranteed minimum number of cards in the same suit.
Treat the 5 cards as pigeons and the 4 suits as holes.
The slide labels and narration explicitly set up this correspondence.
Since , assigning all cards to suits forces crowding in at least one suit.
This is the basic pigeonhole comparison stated by the speaker.
Therefore at least one suit contains at least 2 cards.
This is the conclusion spoken in the audio.
At least 2 cards must have the same suit.
The speaker notes the possibility of "maybe more," confirming that 2 is a guaranteed lower bound rather than an exact count for every distribution.
Speaker asks, "Suppose I have ten cards... What number of cards of the same suit am I guaranteed to have?"
Slide title is "10 Card Draw" and later shows .
Given 10 cards and 4 suits, what is the guaranteed minimum number of cards sharing a suit?
There are 10 cards.
There are 4 suits.
Each card belongs to exactly one suit.
Determine the largest integer lower bound guaranteed for some suit.
Ask whether it is possible to have fewer than 3 cards in every suit.
The slide explicitly poses "< 3 cards in every hole?".
If every suit had fewer than 3 cards, then each suit would have at most 2, giving at most 8 cards total.
This is the contradiction argument spoken by the lecturer.
But there are 10 cards, so the assumption fails.
10 exceeds the maximum 8 allowed under the assumption.
Thus some suit must contain at least 3 cards; equivalently, round up the average .
The formula on the slide and the narration identify the ceiling step.
At least 3 cards must have the same suit.
The speaker adds, "You can check that I needn't have any more, of course," indicating 3 is the sharp guaranteed lower bound in this setup.
Title slide reads “Mathematics for Computer Science,” “MIT ,” and “The Pigeonhole Principle,” with Albert R Meyer and April 24, 2013 at the bottom.
Title text
Course identifier
Lecturer name and date
Small webcam inset
Mouse cursor
Static title slide is shown while the speaker introduces the topic.
The mathematical content is only introduced verbally; no formula is yet displayed.
This segment establishes the lecture topic as the pigeonhole principle.
Text appears in stages: “If more pigeons,” then five pigeon images, then “than pigeonholes,” then four green U-shaped holes.
At about 14 seconds, the slide changes to “then some hole must have ≥ two pigeons!” and the five pigeons are shown distributed among four holes, with one hole containing two pigeons.
Five pigeon images
Four green U-shaped pigeonholes
Text “If more pigeons than pigeonholes,”
Text “then some hole must have ≥ two pigeons!”
Pigeons appear first above empty holes.
The pigeons then move downward into the four holes.
One hole ends up with two pigeons while the other holes contain one pigeon each.
The number of pigeons remains 5.
The number of holes remains 4.
The animation visually demonstrates that distributing 5 objects into 4 containers forces at least one container to hold 2 objects.
Slide shows “Mapping Rule: total injection from A to B implies |A| ≤ |B|.”
A dashed pink box contains “If |A| > |B|, then no total injection from A to B.”
Set symbols A and B
Cardinality notation |A| and |B|
Inequality symbols ≤ and >
Dashed box around contrapositive statement
The previous pigeon animation is replaced by formal set-mapping notation.
The dashed box highlights the contrapositive form.
The slide keeps both the original mapping rule and its contrapositive visible together.
The visual transition connects the informal pigeonhole picture to the formal statement about total injections and cardinalities.
Slide titled “example: 5 Card Draw” shows “set of 5 cards:” and a hand of five playing cards.
Text appears: “must have ≥ 2 with the same suit.”
Next slide labels “5 cards (pigeons)” with five blue card placeholders and “4 suits (holes)” with four blue U-shaped holes above spade, heart, club, and diamond symbols.
The fourth hole’s suit symbol is partly covered by the webcam inset in the sampled view, but the speaker names diamonds and the later layout indicates four suits.
Five playing-card placeholders
Four suit holes
Spade symbol
Heart symbol
Club symbol
Diamond symbol
Text “5 cards (pigeons)”
Text “4 suits (holes)”
The example first states the conclusion about five cards.
It then reformulates the cards as pigeons and the suits as holes.
The mouse cursor points near the suit holes as the speaker names the suits.
There remain 5 card objects and 4 suit categories throughout the example.
The example maps the abstract pigeonhole structure onto playing cards: cards are pigeons and suits are holes.
Five light-blue card placeholders appear above four blue U-shaped containers labeled by suit symbols; arrows point from cards to containers.
5 card placeholders
4 suit containers
spade, heart, club, diamond symbols
arrows
Arrows are drawn from the row of cards down to the suit containers.
Multiple arrows indicate that more than one card may land in the same container.
There remain 5 cards and 4 suits throughout the segment.
The assignment model is one card to one suit.
The picture visualizes the pigeonhole setup: objects are being placed into fewer categories than objects, forcing overlap.
Slide changes to "10 Card Draw", then shows the question "< 3 cards in every hole?", then the formula with an annotation explaining the ceiling brackets.
Title "10 Card Draw"
Question text "< 3 cards in every hole?"
Four suit containers
Formula
Annotation "ceiling, means round up"
The slide first poses the question about whether every hole can have fewer than 3 cards.
It then replaces the question with the computed lower-bound formula.
An annotation points to the ceiling brackets to explain their meaning.
The number of suits remains 4.
The total number of cards remains 10.
The visual sequence tracks the move from an intuitive contradiction question to the compact generalized formula using the ceiling function.
Final slide title reads "Generalized Pigeonhole Principle" and displays the symbolic statement with n, h, and .
Title "Generalized Pigeonhole Principle"
Variables n and h
Formula
The concrete card example is replaced by a fully symbolic statement.
The structure matches the earlier examples: objects assigned to boxes, with a lower bound on some box.
The final slide abstracts the previous numerical examples into the general theorem.
A static slide showing the definition of the Generalized Pigeonhole Principle with a small image of a numbered grid in the top left corner and a webcam feed of the speaker in the bottom right.
Text
Formula
Grid Image
Webcam Feed
Slide content remains static during this interval
The visual presents the formal mathematical statement of the principle being discussed by the speaker.
Screen turns black with white text 'End of slide show, click to exit.' and a mouse cursor.
Black background
White text
Mouse cursor
Indicates the conclusion of the video segment.
Speaker says the pigeonhole principle is “actually just an informal way of saying something that we’ve formally seen already” and later “So we know this rule already.”
One might treat the pigeonhole principle as a separate surprising theorem because its pigeon-and-hole wording sounds informal.
The video clarifies that the informal pigeonhole statement is the contrapositive of the already-known mapping rule: a total injection from A to B implies |A| ≤ |B|.
Speaker defines the failure of a total injection in terms of arrows: no relation has an arrow out of everything in A and at most one arrow into B.
The explanation is intuitive and arrow-based rather than a fully formal definition of functions and injections.
One might think “no total injection” only means some element of A lacks an outgoing arrow.
The video emphasizes that if every element of A must have an outgoing arrow and B has fewer elements, injectivity fails because at least two arrows must enter the same element of B.
Speaker says, "They can't all be below average".
One might think every hole could contain fewer items than the average .
The speaker explicitly rejects this: if all holes were below average, the total could not reach n, so at least one hole must meet or exceed the average and therefore reach the ceiling value.
Speaker clarifies, "these corner braces mean round up to the nearest integer".
Annotation labels the brackets as "ceiling, means round up".
A learner may misread as ordinary grouping or as rounding down.
The video defines the brackets as the ceiling operation, i.e. round up to the nearest integer, which is essential for turning the average into a valid integer lower bound.
Speaker says the informal pigeonhole principle is a way of saying something formally seen among the mapping rules.
Slide replaces the pigeon animation with “Mapping Rule: total injection from A to B implies |A| ≤ |B|.”
The video presents the informal pigeonhole principle as an informal expression of the formal mapping rule for total injections.
Speaker says “taking the contrapositive of that.”
Dashed box states “If |A| > |B|, then no total injection from A to B.”
The formal pigeonhole statement is derived by taking the contrapositive of the mapping rule.
Speaker explains what “no total injection” means using arrows from A to B and two arrows entering the same element of B.
The arrow interpretation unpacks the meaning of “no total injection from A to B” in the contrapositive statement.
Speaker introduces a “much more modest application of the pigeonholing principle” and applies it to five cards and four suits.
Slide labels 5 cards as pigeons and 4 suits as holes.
The five-card example applies the formal pigeonhole principle by treating cards as elements of the larger set and suits as elements of the smaller set.
Card slide states “must have ≥ 2 with the same suit.”
The visual model directly mirrors the earlier five-pigeons-four-holes animation.
The card example is a concrete special case of the informal statement: 5 cards are more than 4 suits, so some suit has at least two cards.
Speaker calls the 10-card case a "slight generalization" of the 5-card case.
Slides progress from "5 Card Draw" to "10 Card Draw".
The 10-card example extends the same pigeonhole reasoning from the minimal case 5 objects into 4 boxes to a larger case requiring the ceiling of the average load.
Speaker moves from the specific 10-card computation to "More generally, if I have n pigeons...".
Final slide states the Generalized Pigeonhole Principle symbolically.
The 10-card, 4-suit result is the instance , of the general theorem .
Speaker defines the corner braces just before stating the general formula.
The theorem uses .
Understanding the ceiling notation is required to interpret the generalized pigeonhole bound correctly.
Speaker states the simple form of the pigeonhole principle.
Slide text gives the informal statement.
Five pigeons are distributed into four holes, with one hole receiving two pigeons.
Speaker says the pigeonhole principle is an informal way of saying a mapping rule and takes the contrapositive.
Slide shows the mapping rule and its contrapositive.
Speaker explains no total injection using arrows out of A and at most one arrow into B.
Speaker states that a set of five cards must have at least two cards with the same suit.
Slide labels 5 cards as pigeons and 4 suits as holes.
Slide explicitly labels “5 cards (pigeons)” and “4 suits (holes).”
Speaker explains that 5 cards and 4 suits force at least two cards into the same suit.
Slide titled "5 Card Draw" maps cards to suits.
Speaker derives the bound for 10 cards by contradiction and ceiling of .
Slide shows .
Speaker says the corner braces mean round up to the nearest integer.
Annotation labels the brackets as "ceiling, means round up".
Speaker states the general rule for n pigeons and h holes.
Slide title is "Generalized Pigeonhole Principle" with formula .
Formula for Generalized Pigeonhole Principle is displayed.
Covered · Title slide and spoken introduction identify the topic as the pigeonhole principle; no formula beyond the title is shown.
Covered · Informal pigeonhole principle is stated in text and demonstrated by five pigeons moving into four holes.
Covered · Slide gives the mapping rule and its contrapositive; speaker explains the connection to total injections and arrow diagrams.
Covered · Five-card draw example is introduced and modeled as 5 card pigeons placed into 4 suit holes; the final spoken clause is cut off but the mathematical claim and visual setup are complete enough to cover.
Covered · Basic 5-card pigeonhole example and its visual mapping.
Covered · 10-card generalization, contradiction argument, ceiling definition, and formula display.
Covered · Symbolic statement of the Generalized Pigeonhole Principle.
Covered · Definition and formula of Generalized Pigeonhole Principle presented.
Covered · End screen with no mathematical content.
Reviewed subject paths
Continue with related videos in the same subject.
YouTube8:13
YouTube6:03
YouTube5:16