Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
17.7.2. Proof using Pigeonhole Principle
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Welcome! Today, we’ll be discussing the Pigeonhole Principle. Can anyone tell me what it is?
Isn't it about putting items into boxes? If you have more items than boxes, some boxes must contain more than one item?
Exactly! This principle is critical in proofs and combinatorial arguments. Let’s see how it applies in different scenarios.
Can we see an example?
Yes, let's consider five distinct points in a plane...
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
...Given five points with integer coordinates, we'll classify them into four categories based on whether their x and y coordinates are odd or even.
So, what will happen with the midpoints?
Using the Pigeonhole Principle, since we have five points, at least two must share the same category, ensuring their midpoint has integer coordinates.
That’s clever! Can you show us the midpoint formula again?
Of course! The midpoint formula is…
I think I understand that now!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let’s move on to selecting five integers from the set of 1 to 8. Who can tell me how we might find pairs that sum to 9?
We can list them? Like, 1, 8 or 2, 7?
Right! Let's categorize our integers into pairs that sum to 9. Now, if we have five integers...
There’s bound to be a match due to the Pigeonhole Principle?
Exactly! If we consider our pairs, we’ll always find at least one pair among any five choices.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Finally, let’s tackle universally quantified statements. Can someone explain what that means?
I think it means it’s true for all cases, right?
Correct! Now we can prove that for every integer, there exists a multiple made up of the digits 0 and 1.
How do we even start?
Let’s define sequences of numbers using 1s, consider their remainders when divided by our integer, and apply the Pigeonhole Principle!
Overview
Short Summary
This section introduces the Pigeonhole Principle and its application in proving the existence of certain pairs within sets.
Medium Summary
In this section, we explore various applications of the Pigeonhole Principle through examples such as distinct points in a plane and pairs of integers whose sum equals a specific value. The principle is used effectively to demonstrate that certain combinations or pairs must exist based on counting arguments.
Detailed Summary
Detailed Summary
In this section, we delve into the Pigeonhole Principle, a fundamental concept in combinatorics that states that if more items are placed into fewer containers than there are items, at least one container must contain more than one item.
We start by examining distinct points in a two-dimensional plane with integer coordinates. Given any five such points, we use the Pigeonhole Principle to show that there always exists at least one pair of those points whose midpoint will have integer coordinates. By classifying each point based on the parity (odd/even) of their x and y coordinates, we establish a mapping to four potential categories; thus, with five points (pigeons) allocated to four categories (holes), at least two points must share the same category.
Next, we extend this reasoning to selecting five integers from the set {1, 2, 3, 4, 5, 6, 7, 8}. We demonstrate that irrespective of the selection, at least one pair will sum to nine, identifying the pairs and applying the mapping approach to elucidate our findings.
The section concludes with a discussion on proving universally quantified statements using the Pigeonhole Principle, exemplified by illustrating how every integer has a multiple composed of only the digits 0 and 1. The method involves constructing numbers of 1s, identifying remainders upon division, and concluding the existence of a suitable multiple.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountTo prove the statement, we will apply the pigeonhole principle. This principle states that if you have more items than containers, at least one container must hold more than one item.
Detailed Explanation
The pigeonhole principle is a fundamental concept in combinatorics. It establishes that if you have 'n' items and 'm' containers, where 'n' > 'm', then at least one container must hold more than one item. In our context, we will identify points as items and categorize them based on their coordinates as containers.
Examples & Analogies
Imagine you have 5 pairs of shoes (items) and only 4 boxes to store them in (containers). When you try to fit each pair into a box, you will inevitably end up with at least one box containing more than one pair of shoes.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountWe will categorize the 5 points according to the parity (even or odd) of their coordinates. There are 4 combinations: (odd, odd), (odd, even), (even, odd), and (even, even).
Detailed Explanation
Each point has both an x-coordinate and a y-coordinate that can either be even or odd. This gives us 4 unique combinations to classify the points. When we analyze 5 points, and since we only have 4 combinations, by the pigeonhole principle, at least two of these points must fall under the same combination.
Examples & Analogies
Think of 4 types of fruit boxes (apples, bananas, cherries, and dates) and 5 fruits you want to place in them. Since you have more fruits than box types, at least one box must end up holding two fruits of the same type.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountFor two points that are categorized the same way, let's consider their midpoint. Given points (x1, y1) and (x2, y2), the midpoint (mx, my) is calculated as ( (x1+x2)/2 , (y1+y2)/2 ).
Detailed Explanation
The midpoint formula allows us to compute the average of the x-coordinates and y-coordinates of the two points. If both x-coordinates are either even or odd, their average will result in an integer. The same applies to the y-coordinates. Thus, we guarantee that both coordinates of the midpoint will be integers.
Examples & Analogies
Imagine two friends standing on a number line at positions 2 and 6 (both even), when they want to meet halfway, they walk to position 4, which is also a whole number. Even if they stood on positions 1 and 3 (both odd), they'd meet at position 2—not a fraction!
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountBy applying the pigeonhole principle, we have shown that no matter how we choose the points, there will always be at least one pair of points whose midpoint has integer coordinates.
Detailed Explanation
In conclusion, our proof illustrates that by categorizing pairs of points according to their coordinates, and leveraging the pigeonhole principle, we can ensure that there exists a pair that confirms our hypothesis about the midpoint's integer nature.
Examples & Analogies
It's like collecting tickets for a concert, where for every two tickets X and Y, knowing both are from the same concert event guarantees that the average location to stand during the show for both tickets is a valid, whole number—because they are different but from the same event!
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Pigeonhole Principle:
A principle used in combinatorics that asserts if n items are placed into m containers, with n > m, then at least one container must hold more than one item.
- Midpoint:
The average of the x-coordinates and y-coordinates of two points, resulting in a point also consisting of integer coordinates.
- Pairs of Integers:
Relates to the concept of summation, specifically identifying pairs that equal a given total.
Examples
Memory aids
If you have more than seats, a few must rest their feet. In pigeonholes so tight, some box must hold more than slight.
Imagine a flock of pigeons trying to fit into their holes, but with so many birds and not enough holes, a few pigeons end up sharing!
Flash Cards
Glossary
Pigeonhole Principle
A combinatorial principle stating that if more items are put into containers than there are containers, at least one container must hold more than one item.
Midpoint
The point that is halfway between two coordinates; mathematically represented as ((x1 + x2)/2, (y1 + y2)/2).
Integer Coordinates
Coordinates in a plane whose values are integers, hence can be represented as (x,y) where x and y are integers.
Ordered Pair
A pair of numbers from a Cartesian product consisting of an 'x' value and a 'y' value, written as (x,y).