Distribution of points on a 5 x 6 rectangle

Question

Prove that if eight points are places in a closed five by six rectangle (closed means that we include the edges) there will be two points that are at most a distance of √10 apart. Use the Pigeon Hole Principle. Type up a formal proof. Be sure to clearly state

(1) What are the pigeons?

(2) How many pigeons are there?

(3) What are the holes?

(4) How many holes are there?

You may draw a picture as part of the proof, but the proof must still be in complete sentences in paragraph form.

Answer 1

Dissect the rectangle into seven cells as shown in the figure. By the pigeonhole principle, there must be a cell which contains at least two of the eight points. The maximum distance between two points in any one cell is $\sqrt{10}$.

Answer 2

Hint: you can subdivide the $5 \times 6$ rectangle into 7 rectangles that each have a diagonal shorter than $\sqrt{10}$. Then you can indeed apply the pidgeonhole principle with the points as pidgeons, and the smaller rectangles as holes.