Associated Topics || Dr. Math Home || Search Dr. Math

### Proof with Pigeonhole Principle

```
Date: 09/20/2001 at 23:14:55
From: Matt Hudson
Subject: Proof with Pigeonhole Principle

Given five points on a plane with integer coordinates, prove that some
pairs have a midpoint whose coordinates are also integers.
```

```
Date: 09/21/2001 at 05:06:15
From: Doctor Floor
Subject: Re: Proof with Pigeonhole Principle

Hi, Matt,

Thanks for writing.

Divide the points with integer coordinates into the following groups:

1. x odd, y odd;
2. x even, y odd;
3. x odd, y even;
4. x even, y even.

I leave it to you to show that if two points are from the same group,
then their midpoint has integer coordinates.

From the pigeonhole principle it is clear that from five points, there
must be two in the same group.

If you need more help, just write back.

Best regards,
- Doctor Floor, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search