Application of Pigeonhole Principle

Today, we're going to explore the Pigeonhole Principle. It's a fascinating concept in mathematics that tells us that if we have more items than containers, at least one container must hold more than one item. Can anyone give me an example?

If I have 5 apples and only 4 baskets, then at least one basket will have at least 2 apples!

Exactly! Now, let's see how this principle applies to our first problem regarding points in a 2D plane. We’ll analyze 5 distinct points with integer coordinates.

What’s the goal with these points?

Our goal is to demonstrate that from these 5 points, there are always at least two points whose midpoint has integer coordinates. Let’s categorize the points based on their x and y coordinates.

Are we grouping them by if they're odd or even?

Yes! There are four combinations: both x and y even, both odd, one odd and one even. Since we have 5 points but only 4 combinations, what does that mean?

Using the Pigeonhole Principle, at least two points must share a combination!

Exactly! This guarantees that their midpoint will also be an integer. Great start!

Now, let's consider specific examples with these points. For instance, if we have points A(1,2) and B(3,4), how do we find their midpoint?

We can use the formula for the midpoint: M = ((x1+x2)/2, (y1+y2)/2).

Correct! In this case, what would M be?

M would be ((1+3)/2, (2+4)/2), which is (2, 3)!

Excellent! Now, since we knew that those points shared the same parity for both coordinates, we conclude M also has integer coordinates. This is how the Pigeonhole Principle leads to reliable results.

So it works for any pair of points that share that characteristic?

Yes, that’s correct! It applies universally in these scenarios.

Let's shift our focus to selecting integers from the set {1, 2, ..., 8}. What happens when we choose 5 of those integers?

I think we can find at least one pair that sums to 9.

Yes! Can anyone give me the pairs that sum to 9?

There’s (1, 8), (2, 7), (3, 6), and (4, 5).

Perfect! We have four pairs, and since we pick 5 integers, the Pigeonhole Principle tells us that at least two integers must belong to the same pair. What does this imply?

That we can always find at least one pair that sums to 9!

Exactly right! This shows the practical application of the principle in various numeric contexts.

Finally, let's explore a universally quantified statement involving integers. Can someone summarize what we need to prove?

We want to prove that for any integer n, we can find a multiple that only contains the digits 0 and 1.

Yes! We construct numbers having up to n+1 digits with only 1's. What do you think about their remainders when divided by n?

There will be n possible remainders!

Correct! Since we are creating n+1 numbers, the Pigeonhole Principle indicates that at least two must share the same remainder. Can anyone think of what happens next?

That means we can find a number composed solely of 1's and possibly some leading 0's, which will be divisible by n!

Exactly, excellent work everyone! This showcases a powerful method of problem-solving.