The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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   
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.