Show that two points must be there with distance less than 5

34 Views Asked by At

Given a rectangle 12 x 20 and 21 points within it, there must be two points that are less than 5 units apart.
My thoughts:
I tried dividing the rectangle by drawing a horizontal line in the middle and 10 vertical lines, which makes 20 small boxes of size 6 x 2. Since there are 21 points, two must lie inside the same box. The diagonal of the box = sqrt(36+4) = sqrt(40) which comes to >5 units so this strategy of proof fails. Not sure if there could be an alternative way to divide the rectangle and apply pigeon hole principle

1

There are 1 best solutions below

0
On BEST ANSWER

Divide the rectangle into twenty $3\times4$ small rectangles. At least one of the small rectangles must contain two points. The diagonal of the small rectangle is $5$. So there must be two points within $5$ units from each other.