Discrete Mathematics

Today, we will explore the concept of midpoints among distinct points in the 2D coordinate plane. Can anyone tell me how to find the midpoint between two points?

Isn't it by averaging the x-coordinates and y-coordinates of the two points?

Exactly! The midpoint M of points (x1, y1) and (x2, y2) is calculated as M = ((x1 + x2)/2, (y1 + y2)/2). Now, let's assume we have 5 distinct points with integer coordinates. Who can think of how we might use the pigeonhole principle here?

We could categorize the points based on whether their x and y coordinates are even or odd.

Right! Each point can have 4 combinations: even-even, even-odd, odd-even, and odd-odd. Since we have more points than combinations, we can be sure that at least two points will fall into the same category.

So those two points will have the same parity for both coordinates, meaning their midpoint will be an integer?

Exactly! This is a great application of the pigeonhole principle. Remember the acronym PIGEON - Pairing Integers Guarantees Existence Of Number.

Can you give us an example?

Sure! Consider points (1,3), (2,4), (3,5), (4,6), and (5,7). We can see two of these points, like (2,4) and (4,6) share the same parity. Their midpoint indeed has integer coordinates.

To summarize, we used the pigeonhole principle to show that with 5 points, there will always be a pair for which the midpoint is an integer.

Now, let’s discuss the second problem of picking five integers from 1 to 8 and proving that at least one pair of them sums to 9. Can anyone recall which pairs of numbers from this set add up to 9?

We have (1,8), (2,7), (3,6), and (4,5).

Great! If we set these pairs as holes in the pigeonhole scenario, what do we consider as pigeons?

The five integers we select from the set.

Correct! Since we have only 4 pairs but 5 numbers, by the pigeonhole principle, there must be at least one repeated pair among the selections, ensuring that at least one pair sums up to 9.

So any choice of 5 will always include a pair that sums to 9!

Precisely! It’s like a game where with too many players, some will inevitably share spots. Remember: sums produce pairs in pigeonholes.

Can we derive this non-graphically?

Definitely! Mathematically, it’s straightforward to see that when choosing any 5 integers, they map directly onto those pairs.

To recap, selecting any 5 integers from 1 to 8 will always generate at least one pair that sums to 9, thanks to the pigeonhole principle.

Lastly, we’ll prove a universally quantified statement regarding integers. Can anyone share a number that consists of only the digits 0 and 1?

What about 1 or 10?

Great examples! We want to show that for any integer n, there exists a multiple of n that has only 1s and 0s in its decimal representation. How might we use what we've learned?

We can set up remainders! Count those numbers that only have 1s.

Excellent! By creating sequences of numbers with increasing 1s (1, 11, 111...), we can derive their remainders when divided by n.

And if we have more remainders than numbers, the pigeonhole principle assures two numbers will share a remainder.

Exactly! Therefore, the difference will be a decimal number made up only of 1s and 0s, which is a multiple of n.

So, for any integer, we can always construct multiples with just 1s and 0s?

Absolutely! That showcases the elegance of the pigeonhole principle. To summarize, for every integer n, we can find a multiple composed entirely of 1s and 0s.