3

What is the minimum number of points randomly chosen in a $4\times4$ square (each point can be at the square's boundary) so that there is always a pair of $2$ points not more than $\sqrt2$ units apart?

Let the number of points be $n$. We can divide the square into $16$ unit squares. If $n\ge17$, by the pigeonhole principle, then at least one unit square has multiple points, and the distance of those points is not more than $\sqrt2$. If $n=16$, it can happen that no unit square has multiple points. But, I have not been able to construct an example where every $2$ points are more than $\sqrt2$ units apart.

How to construct an example of the distribution of $16$ points in the large square such that every $2$ points are more than $\sqrt2$ units apart? If such an example cannot be constructed, why, and what is the maximum number of points such that it is possible that every $2$ points are more than $\sqrt2$ units apart?

My attempt:

Put $4$ points near the bottom, horizontally $1\frac13$ units apart, as in this picture:![the image

But I don't know how to continue.

user_194421
  • 2,291
  • You need examples of points more than $\sqrt 2$ units apart. The answer is "one more than the maximum number of points so that no two are within $\sqrt 2$ units of one another." It doesn't sound like a pigeonhole problem to me. – saulspatz Apr 02 '18 at 01:48
  • 2
    Hmm... this seems to become the circle packing problem of trying to pack circles of radius $\frac{\sqrt{2}}{2}$ into a square of side length $4+\sqrt{2}$ (extend the margins of the square by $\frac{\sqrt{2}}{2}$ in each direction since the points in our original problem correspond to centers of circles and the points could have been on the outer edge of the original grid) – JMoravitz Apr 02 '18 at 01:51
  • The ratio of the radius of the circles to the side-length of the square in this case would be $\frac{\sqrt{2}/2}{4+\sqrt{2}}\approx 0.1306\dots$. According to this page, this would seem to imply the true maximum number of points that can fit in the square without two being within range of one another would be $13$ and fitting $15$ would be impossible. (or I could be reading it incorrectly and its actually $12$)... – JMoravitz Apr 02 '18 at 01:57
  • 1
    This page provides similar information as well as nice visuals, except being phrased in terms of a unit square like the earlier link, it is phrased in terms of unit circles. – JMoravitz Apr 02 '18 at 02:04
  • That solved the problem. – user_194421 Apr 02 '18 at 02:11

0 Answers0