Why Does Placing 26 Points in a 15x20 Rectangle Guarantee Close Proximity?

[sam400]

<<Mentor note: Missing template due to originally being posted in other forum.>>

So, my professor gave a problem which stated:

Given a 15 x 20 rectangle, prove that if 26 points are chosen, at least one pair will be at most five units away.

What I said was to split the rectangle into 12 5x5 squares. Then, at least 1 square will have at least 3 points, since if each of them had 2 points, it would only add up to 24. from there, I went on to say that the longest distance between 2 points in one of the smaller squares is 5 root 2 units. But since one of them will have a third point, the next longest distance possible for that point is 5 units, which is the length of one side.

My professor's explanation was much more eloquent, since he just divided the rectangle into 25 3 x 4 rectangles, then by pigeonhole principle, one of the rectangles will have two points, and the diagonal length will be 5.

While his explanation is much smoother than mine, he said my explanation was entirely wrong as well, but I forgot to ask him why that is. I could understand it being bad since it's so much longer, but I'm not sure what else there is.

 

[Orodruin]

from there, I went on to say that the longest distance between 2 points in one of the smaller squares is 5 root 2 units. But since one of them will have a third point, the next longest distance possible for that point is 5 units, which is the length of one side.

This is wrong. You can have three points inside a square with side five without either being closer than five. Consider the points: (0,0), (1,5), (5,1)

 

[sam400]

oh, so the diagonal is the longest distance only for a rectangle?

 

[Orodruin]

oh, so the diagonal is the longest distance only for a rectangle?

The diagonal is still the longest distance, but since the diagonal is quite a bit longer than 5, you do not need to put two points in opposite corners. There are other configurations, some of which will lead to a possibility of placing a third point more than 5 units away from both of the previous points.

 

[certainly]

at least one pair will be at most five units away.

This statement is a little ambiguous, (or perhaps confusing is a better word), I think your question should be phrased like this:- If 26 points are chosen at random inside a 15$\times$20 rectangle, than there exists at-least one pair of points the distance between which is less than or equal to 5 units.