Prove at least two points in a rectangle are within $\sqrt{5}$ of each other

I've seen problems involving unit square and unit triangles, where the question asks if there are $5$ points, at least two are within $\frac{\sqrt{2}}{2}$ and $\frac{1}{2}$ respectively.

But when the shapes are not same-sided, I get confused. I have a $3\times 4$ rectangle and I have six points. There should be at least $2$ points within $\sqrt{5}$ of each other. I assume first you have to divide the rectangle to 5 equal parts and make the points at least $\sqrt{5}$ from another and prove using the pigeon hole principle. But I don't know how to partition the $3\times 4$ rectangle into $5$ pieces so that's where I'm stuck.

• @MarkBennet My bad! It's been corrected. Apr 26, 2014 at 8:47

Construct the rectangle and divide it into $12$ squares.Now denote the rightmost bottom intersection as $A_1$ and the next to it as $A_2$ and so on. Denote the intersection just above $A_1$ as $B_1$ and so on. Now for the five regions to which we will apply PHP will be- 1. $A_1B_1C_2B_3A_3$ , 2. $A_3B_3C_4B_5A_5$ , 3. $B_5C_4D_4D_5$, 4. $D_4C_4B_3C_2D_2$ and 5. $C_2D_2D_1B_2$.

• How 6 squares?? It should be rectangles right?? accordingly the second half should change. Apr 26, 2014 at 9:11
• I was wrong. Deleted my answers. Thanks for sticking to ur argument :) .
– user67773
Apr 28, 2014 at 14:43
• But now, I am trying to figure this out: thinking from the Pigeonhole angle, there should be a way to cover this rectangle by 5 disks of radius $\sqrt{5}/2$.
– user67773
Apr 28, 2014 at 14:51
• @Umakant: My earlier proof had been wrong. See this proof using PHP. Apr 29, 2014 at 7:10
• Cool. The Ed. Pegg tiling. Thanks @William
– user67773
Apr 29, 2014 at 7:47

HINT: The parts don't need to be equal. Nor do they need to be disjoint, provided that when two points are in the same part they meet the constraint (though if parts overlap you can allocate the overlap between parts to make them disjoint if necessary).

Where would you put five points so they are as dispersed as possible within the rectangle? One place to start is by creating regions around those points (bearing in mind that the best arrangement for six points might be different, so you need to control the diameter of each piece).

• Note, for another thought, that if you can cover each region with a circle of radius $\frac {\sqrt 5} 2$ you will meet the constraint, so you might want to work out the best arrangement of five circles. Apr 26, 2014 at 9:01