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.6.1. Identifying Pigeons and Holes
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we are going to discuss the pigeonhole principle. This simple yet powerful concept shows that if you have more items than containers, at least one container must hold more than one item. Can anyone give me an example of this principle?
If I have 10 socks but only 9 drawers, at least one drawer will have more than one sock.
Exactly! Great example. Now, let’s apply this principle to our mathematical problem involving points in a two-dimensional plane.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Imagine we have five distinct points, each with integer coordinates. The goal is to prove that no matter how we choose these points, at least one pair will have a midpoint that also has integer coordinates. Let's identify the nature of their x and y coordinates.
Are we looking at even or odd coordinates?
Exactly! We can have four combinations: (even, even), (even, odd), (odd, even), and (odd, odd). Now if we map our five points to these four combinations, what does that imply?
By the pigeonhole principle, since we have more points than combinations, at least two points must map to the same combination!
Correct! And what does that tell us about their midpoints?
Their midpoint will have integer coordinates because both points share the same evenness or oddness!
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now, let’s consider a different example: if you choose 5 integers from the set {1, 2, 3, 4, 5, 6, 7, 8}, can anyone tell me what must be true about their sums?
There should be at least one pair of numbers that adds up to 9!
Exactly! Let's identify the pairs that equal 9: (1, 8), (2, 7), (3, 6), and (4, 5). What does applying the pigeonhole principle tell us about these pairs?
Since there are four pairs but five integers, at least one selected integer must be part of a pair that sums to 9.
That's right! This proves the applicability of the pigeonhole principle in our example.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Next, let’s tackle a universally quantified statement. It states that for any integer k, there exists a multiple of k that consists only of digits 0 and 1. How do you think we should approach this?
Maybe we can create numbers made of just 1’s and see if they are divisible by k?
Great thought! We construct numbers made solely of 1’s, check their remainders when divided by k, and apply the pigeonhole principle to find a match.
So, we establish at least two of these numbers will yield the same remainder?
Exactly! And this leads to concluding that their difference is a multiple of k, showcasing the principle in a numerical context.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Let's recap our discussions on the pigeonhole principle and its applications. We started with identifying midpoints, then moved to integers that sum up, and finally, we explored universally quantified statements.
I really see how the pigeonhole principle provides concise proof for each scenario!
I see it as a way to demonstrate certainty in mathematics.
Excellent insights! Remember, strategies like the pigeonhole principle are not just tools but foundational aspects of mathematical reasoning.
Overview
Short Summary
This section illustrates the application of the pigeonhole principle through examples involving coordinate points and integers.
Medium Summary
The section explores the pigeonhole principle through distinct points in a two-dimensional plane, proving that certain conditions will always yield integer midpoints. It also demonstrates how selecting integers from a range guarantees pairs that sum to a specified number using the pigeonhole principle.
Detailed Summary
In this section, the pigeonhole principle is introduced as a fundamental counting strategy to demonstrate relationships between sets of items, particularly in mathematical proofs. The first example involves five distinct points on a two-dimensional plane with integer coordinates. By determining the parity of x and y coordinates (even or odd), we conclude that at least one pair of points always yields an integer midpoint, due to the limited combinations of parity available.
The second example expands on the pigeonhole principle by demonstrating that selecting five integers from the set of integers 1 to 8 will always result in at least one pair of integers summing to 9. Here, ordered pairs that produce this sum are identified, reinforcing the principle as we apply it to both geometric and numerical contexts. These two examples together illustrate the powerful implications of the pigeonhole principle in mathematical reasoning.
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 accountYou are given here arbitrary distinct points in 2 dimensional planes. Each point will have an x-coordinate, y-coordinate and the points are having integer coordinates. So they are arbitrary points except that they are distinct.
Detailed Explanation
We start by considering a set of distinct points in a two-dimensional plane. Each of these points has specific integer coordinates defined by their x and y values. The uniqueness of these points suggests that no two points occupy the same position in this plane.
Examples & Analogies
Think of each point as a unique location on a city map, where every location is identified by its specific address (x, y coordinates). Just like no two houses can have the same address, no two points in our scenario can have the same coordinates.
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 accountOur goal is to show that irrespective of the way these 5 points are chosen arbitrarily there always exist a pair of points such that if you consider the midpoint of the line joining those 2 points it has integer coordinates.
Detailed Explanation
We aim to demonstrate that among any 5 points, at least one pair will yield a midpoint with integer coordinates. To find the midpoint between two points, the formula used is the average of the x-coordinates and the average of the y-coordinates.
Examples & Analogies
Imagine you're standing at two bus stops represented by our distinct points. The midpoint is the perfect stop halfway between them where you can catch a bus. Surprisingly, no matter how you pick your bus stops (the distinct points), there's always going to be a halfway point that lands exactly on an integer bus stop.
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 apply the pigeonhole principle, we must identify the set of pigeons and the set of holes. Here, we identify the set of 5 arbitrary points and map them based on the evenness or oddness of their x and y coordinates, leading to 4 possible combinations.
Detailed Explanation
In applying the pigeonhole principle, we categorize the results based on whether the coordinates are even or odd. There are four combinations possible for assigning each point based on its coordinates. Since there are 5 points (pigeons) and only 4 combinations (holes), at least one combination must be repeated.
Examples & Analogies
Picture a situation where you have 5 different shoes (pigeons) to fit into just 4 boxes (holes). No matter how you try to distribute them, at least one box will end up with two shoes, just like at least one coordinate combination will have two points associated with it.
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 accountSince two points are guaranteed to share the same ordered pair (odd/even), we conclude that their midpoint must have integer coordinates.
Detailed Explanation
From our established mapping, we know two points share the same type (both odd or both even for x, likewise for y). Thus, when computing the midpoint, both x-coordinates will sum to an even number, ensuring that the midpoint coordinates are integers.
Examples & Analogies
Returning to our bus stop analogy, if both stops you picked are located on even-numbered streets, the stop halfway between them will also land on an even-numbered street, proving it results in a clear, integer coordinate on the map.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Pigeonhole Principle:
If you have more items than containers, at least one container holds more than one item.
- Midpoint Formula:
The formula to calculate the midpoint between two points.
- Integer Coordinates:
Points on a grid where all coordinate values are integers.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
If you have 5 points - (1,1), (2,2), (3,3), (4,4), (5,5) - the possible combinations of parity will show that at least one pair will have an integer midpoint.
Choosing numbers 1 to 8, pairs like (1,8), (2,7), etc. will always sum to 9 if 5 integers are selected.
Memory aids
Imagine a classroom with 10 students but only 8 desks, guaranteeing at least 2 students share desks, illustrating the pigeonhole principle.
Flash Cards
Glossary
Pigeonhole Principle
A counting principle which states that if more items are put into fewer containers, at least one container must contain more than one item.
Midpoint
The point that is exactly halfway between two given points in a geometric space.
Integer Coordinates
The set of points in a 2-D plane where both x and y coordinates are integers.