Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $R$ be a rectangular region with sides $3$ and $4$. It is easy to show that for any $7$ points on $R$, there exists at least $2$ of them, namely $\{A,B\}$, with $d(A,B)\leq \sqrt{5}$. Just divide $R$ into six small rectangles with sides $2$ and $1$ and so at least one such rectangle must contain $2$ points from the seven ones. Thus the result follows.

Here is the question:
What about six points?

I believe that the same is true. How do I prove my belief?


ps: I don't want to find such $6$ points. I'd like to show it for any set with $6$ points.

share|improve this question
    
Five points can be this far apart. Just do a greedy algorithm along the perimeter. –  Jp McCarthy Jan 16 '13 at 22:52
    
@JpMcCarthy, sorry. I didn't follow your comment. What should I do with five points? –  Sigur Jan 16 '13 at 22:53
    
Problems like this are usually very easy (like your seven point example) or very hard. You can argue that you must either have a point in the corner or one on each of two connected edges, because given a solution you can slide the rectangle to make this true. Then you can try to catalog all the configurations and show that none work. Sometimes you can be clever by calculating the area of the exclusion zones of five points and show there isn't any left, but overlaps make that difficult as well. The easy way for six points would be to prove your belief incorrect by finding a set. –  Ross Millikan Jan 16 '13 at 22:54
1  
For the five points, just start with a point in the corner, proceed $\sqrt 5 + \epsilon$ around the perimeter, swing a compass from that point to get the next, and continue. They fit. –  Ross Millikan Jan 16 '13 at 22:55
    
I believe OP is asking how high he can increase the maximum of the minimum distance. This is not clear in the way he has it phrased. –  Calvin Lin Jan 16 '13 at 22:57

2 Answers 2

up vote 6 down vote accepted

The problem and solution are in Jiri Herman, Radan Kucera, Jaromir Simsa, Counting and Configurations: Problems in Combinatorics, Arithmetic, and Geometry, page 272. Let the rectangle have corners $(0,0),(0,3),(4,0),(4,3)$. Draw line segments joining $(0,2)$ to $(1,1)$ to $(2,2)$ to $(3,1)$ to $(4,2)$, also $(1,1)$ to $(1,0)$, $(2,2)$ to $(2,3)$, and $(3,1)$ to $(3,0)$. This splits the rectangle into $5$ pieces, and it's not hard to show two points in the same piece must be within $\sqrt5$.


A picture to illustrate the solution.

enter image description here

share|improve this answer
    
@Sigur, thanks! –  Gerry Myerson Jan 16 '13 at 23:30
    
I have to thank you. If you haven't told me I wouldn't find that book. Thanks. –  Sigur Jan 16 '13 at 23:31

For a different approach, also start by observing that any rectangular area with sides 2 and 1 can contain at most one point if any two points are to be more than $\sqrt{5}$ apart. Now note that 2-by-1 rectangles can be placed horizontally (blue in illustration below) or vertically (green). So we can...

Split the 4-by-3 rectangle into 12 unit size squares, color like a chessboard (black and white such that no squares sharing an edge have the same color). Consider a pair of neighboring squares: If they contain (at least) two points, these have a distance $\leq \sqrt{5}$. If they contain no point, there must be another pair of adjacent squares with two points (pigeonhole principle, five 2-by-1 rectangles/square pairs left for six points), whose distance is then $\leq \sqrt{5}$. If each black/white pair of adjacent squares contains exactly one point, it follows that the points must be either all on black or all on white squares (there are exactly 6 of each).

colored squares and diagonal illustration

Then, in either case there must be a "diagonal" of three squares with one point each (* or x in illustration). Now imagine the middle square split along the other diagonal. Now for each triangle, every point in or on it is no farther than $\sqrt{5}$ from any point in the respective closer, diagonally "neighboring" square! (In other words, w.r.t. to the illustration, if the point in the middle square is closer to the top left, it is less than $\sqrt{5}$ from the point in the top left, otherwise it is within $\sqrt{5}$ distance of the point in the lower right square.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.