Five Lattice Points

Five Lattice Points: What is that about?
A Mathematical Droodle

The blue dots below are draggable.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Discussion

If five nodes of a plane lattice are chosen at random, some two of them define a line that contains other lattice points, and more specifically, the midpoint of the segment between the two points is necessarily a lattice point. Four points may not possess such a pair. The applet above illustrates this statement in case of the square grid.

The validity of the statement for four points is easily established with the help of the applet. The case of five points is also simple.

The midpoint of the segment joining points P(x₁, y₁) and Q(x₂, y₂) is given by M((x₁ + x₂)/2, (y₁ + y₂)/2). M is the lattice point if and only if x₁ and x₂ are of the same parity and so are y₁ and y₂. With 2 coordinates, there are four different parity pairs: odd/odd, odd/even, even/odd and even/even. Among five points, at least two are bound to have the same parity combination. The line joining any two such points is bound to contain other lattice nodes.

The proof makes use of the Pigeonhole Principle: If n objects are distributed between fewer than n boxes, at least one box must contain at least two of the objects.

References

M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
B. Averbach, O. Chein, Problem Solving Through Recreatinoal Mathematics, Dover, 2000
M. Gardner, The Last Recreation, Copernicus, 1997
R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

71536667