Let $R$ be a $4 \times 4$ square. For any seven points on $R$, there exists at least two of them, namely $\{A,B\}$, with $d(A,B)\le\sqrt{5}.$

(Old problem):

If $R$ is a rectangular region with sides $3$ and $4$, for any six points on $R$ we can prove there exist at least two of them, namely $\{A,B\}$, with $d(A,B)\le \sqrt{5}$.

We can divide $R$ in five pieces, see solution.

But my problem is that I can't divide $R$ in six pieces. Can you help? I think this is an interesting problem.

Sorry, I have already drawn a figure, divided $R$ seven pieces, and I can't upload, I don't know why. I posted this question on MO.

enter image description here

  • $\begingroup$ I have added the picture from you MO post here (since you write that you cannnot upload images). However, isn't the question already answered by that figure? $\endgroup$ – Martin Sleziak Sep 6 '14 at 13:56
  • $\begingroup$ It is also worth mentioning that the picture seems to be adapted from math.stackexchange.com/questions/280362/… $\endgroup$ – Martin Sleziak Sep 6 '14 at 14:00
  • 1
    $\begingroup$ @MartinSleziak if you can partition a $4 \times 4$ square into 7 pieces whose diameter are all $\le \sqrt{5}$, you have shown that given any $8 = 7+1$ points, at least two of them are at a distance $\le \sqrt{5}$. To show the statement in question, you need to partition the square into $6$ instead of $7$ pieces. $\endgroup$ – achille hui Sep 6 '14 at 14:05

To only prove the assertion, start by cutting the square in eight $2\times 1$ rectangles.

                                                                 enter image description here

Because there are seven points, there is a rectangle with no points. By symmetry, we have two cases to consider. They are

                                             enter image description here enter image description here

We will work in the first case only, as the second is similar. Suppose no points are $\leq \sqrt 5$ away. There are seven rectangles and seven points. If there are two points in one rectangle, the problem is over. From now on, assume then that every rectangle has exactly one point. Now, color it as a checkboard.

                                                                 enter image description here

By the pigeonhole principle, there are at least four points in black squares or at least four points in white squares. However, if a point is in a certain square, there aren't points in its side neighbors. You can check that no matter which four squares of some color you choose, no squares of the other color may have points.

That way, the points are either in white or in black. We will choose the white case, as again the black case is very similar. Choose the following three diagonally related squares and paint them in a special way.

                                                                 enter image description here

Because there is a point in the upper square, the point in the medium square cannot be in the greenish region, as in these regions any two points have distance $\leq \sqrt 5$. But, because there is a point in the lower square, the point in the medium square cannot be in the yellowish region either. This contradicts the fact that every two points are separated by $>\sqrt 5$. $\square$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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