Wednesday, April 17, 2013

The 5 Integer Points Puzzle

An integer point is a point whose coordinates are integers.

Suppose we arbitrarily choose 5 integer points.

 Find the way to prove that we can always find 2 among these 5 integer points such that the line segment joining the 2 points contains at least 1 more integer point.


  1. If the delta between two points has two even components then there is an integer point half way between them. Also, the delta between two points is the delta between their corresponding deltas to a common point. That is, (C-B) = (C - A) - (B - A).

    There are four deltas from A, (B-A), (C-A), (D-A), (E-A), and there are four possible even/odd combinations. If one combination is repeated by two deltas, then that pair's delta is even/even. If no combination is repeated, one of the deltas must already be even/even.

  2. I think this could work?

    A line connecting two integer points have no internal points if the difference in their x coordinates is coprime to the difference in their y coordinates. Otherwise, if the x and y differences of two points were both divisible by 2, for example, then the midpoint of the line connecting them would have integer coordinates.

    So then, considering only evens and odds, if we have any point at some coordinate (x,y), we cannot place another point (x', y') where x' has the same parity as x , and y' has the same parity as y. But since there are only four varieties of points - (even, even), (even, odd), (odd, even), and (odd, odd) - with five points we must have at least two of a single type (and then their difference in coordinates would be of the form (even, even), and so their midpoint would have integer coordinates).