2
$\begingroup$

Q:Consider the 2D grid with integer coordinates.Prove that if we take 5ve points on the grid then there exist two of the points whose average is also a point on the grid.

I understand the basic idea behind Pigeon Hole principle, but I just cannot see how to apply it to this problem.

Here is my attempt to solve it.


There is always two integers in the set of five whose sum is even since if their sum is odd then there is another integer number whose sum with one of these numbers is going to be even. I apply this logic to x and y coordinates.

I had another idea of defining my pigeons as the number of all possible averages of two points from 5 points, and my pigeon boxes as the average is an integer and the average is not an integer.

Can someone give me hint on the direction of solving this problem. Thank you.

$\endgroup$
4
$\begingroup$

Look at the parity of coordinates, there are only $4$ options: $$(\text{even},\text{even}), (\text{even},\text{odd}), (\text{odd},\text{even}), (\text{odd},\text{odd})$$ So at least $2$ of the points fall in the same category, meaning the differences of $x$ and $y$ coordinates are both even, so there's a midpoint.

$\endgroup$
  • 1
    $\begingroup$ Ohh! I see it now. Thank you :D $\endgroup$ – Basil M. Nov 16 '14 at 20:29
  • 1
    $\begingroup$ @BasilM. I know you can't upvote yet, but there's this extremely small checkbox under the arrows which allows you to accept the answer. I'm saying this just in case you didn't notice it as you are new to this site. $\endgroup$ – user2345215 Nov 16 '14 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.