6

Prove that having 6 points in the interior of a square of side length 3, we can choose 2 of them so that the distance between them is less than 2.

Looks obvious, but I can't get a rigorous demonstration.

I tried to cover the square with 6 circles of radius 1, having the centers inside the square, to prove they must intersect at least once.

Note:

This partition leads to solution.

The rectangles on the first row: $3/2 * (3 - \sqrt3) $

The rectangles on the second row: $1 * \sqrt3 $

The 5 zones are so that the distance between any 2 points inside the same zone is less than 2.

enter image description here

  • I think the idea is to split the square into 5 zone so that the distance between any 2 points inside the same zone is less than 2. The, applying the box principle, comes the result. Each zone might be a rectangle or square. –  Aug 19 '15 at 20:48

4 Answers4

4

I post here a slightly more elaborate version of OP's answer included in the question.

It suffices to partition the square into $5$ sets of diameter less than $2$; then two of the points will be within the same set. Consider this partition:

rectangle

where the rectangles of the second row are of height $h<\sqrt{3}$. This ensures that these rectangles, being of size $1\times h$, have diagonal strictly less than $2$.

The rectangles on the first row are of size $3/2$ by $3-h$. We need their diagonals to be less than $2$, which means $$ \frac{9}{4} + (3-h)^2 < 4 $$ This inequality is equivalent to $3-h < \sqrt{7}/2$, i.e., $h>3-\sqrt{7}/2$. Since $$ 3-\sqrt{7}/2 < \sqrt{3}$$ (easy to check by squaring, etc) it follows that it's possible to pick $h$ so that all diagonals are strictly less than $2$.

One can also use $h=\sqrt{3}$ if only nonstrict inequality is desired, or if the points are constrained to the interior of the square (as here).

1

Consider breaking up the square into $16$ pieces as shown.

Square

These $16$ squares have side lengths $3/4$ and the maximum distance between any squares that are adjacent horizontally or vertically is $\sqrt{(3/4)^2+(3/2)^2} < 2$. Now suppose we have not put in any points inside our square and we will put in the points one by one. Putting a point in any square eliminates that square as well as other any squares that are adjacent vertically or horizontally to it. Through some tedious casework/consideration, we can show that any arrangement of $5$ points inside the square either has two points in adjacent squares or eliminates the entire board. Using this argument, we can actually strengthen the claim to say a square with side length $\frac{8}{\sqrt{5}}$ has this property.

Sandeep Silwal
  • 8,135
  • The casework is actually not all that tedious -- only the squares in the corners have only two neighbours, and there are only four of them -- so at least one point is in a square with three neighbours, so at least $4\cdot3+4=16$ squares are eliminated. – joriki Aug 19 '15 at 20:32
  • One way to rephrase part of this argument is in terms of the graph whose vertices correspond to the smaller squares, and edges correspond to vertical/horizontal adjacency; one needs to show that this graph has no independent vertex set of size 6. – Greg Martin Aug 19 '15 at 20:32
  • Hmmm. What about the six subsquares consisting of the four along the main diagonal, together with the other two corners? Any subset of size 5 fails to cover all 16 subsquares. – Greg Martin Aug 19 '15 at 20:34
  • @GregMartin: Hmm that might be the only dud case I think? Thanks for pointing it out. – Sandeep Silwal Aug 19 '15 at 20:39
  • @Sandeep Silwal I think I found the solution, see my comment –  Aug 19 '15 at 20:52
1

Not as elegant as the five rectangles. But if you just start swinging arcs of radius 2 all over the place, you can build this:

enter image description here

The midpoint on the bottom edge is a true midpoint (meaning it's $3/2$ from each of the lower corners). There are four darker zones that each have diameter $2$, and each dotted line is illustrating that diameter $2$. The fifth "zone" is made of those last two lighter areas, and clearly has diameter less than $2$.

2'5 9'2
  • 54,717
0

Rather, what you should do is show that the square can be covered by five circles of radius 1. (Line three of them up near the top of the square and the other two near the bottom.) Then, any set of six points must, by the pigeonhole principle, have two of its points inside the same circle; those two points are at most 2 units apart.

Greg Martin
  • 78,820