We take $n$ arbitary points on or inside a square of side $2cm$ such that there will always be a pair of points at a distance of not more than $2cm$. What is the minimum value of $n$?
$(1) 2$
$(2) 4$
$(3) 5$
$(4) 8$
I have no idea how to approach this problem. Maybe Sylvester-Gallai theorem could help but I don't think I can use it. Please help
On
The vertices are four points that are 2 cm apart. Any fifth point will be less than 2 cm from at least one of the vertices.
On
Alternate proof using $1$-norm / Manhattan distance:
Assume (for later contradiction) that the 4 points are s.t. each pair is $> 2cm$ apart. Divide the $[-1,1] \times [-1,1]$ square into 4 separate $1\times 1$ smaller squares and applying the pigeonhole principle, it is clear that the 4 points must reside one per smaller square. Starting from the point inside $[0,1] \times [0,1]$ name the 4 points clockwise as $p_i = (x_i, y_i)$ for $i = 1, 2, 3, 4.$
+---+---+
| p4| p1|
+---+---+
| p3| p2|
+---+---+
Now consider $X = |x_1 - x_2| + |x_2 - x_3| + |x_3 - x_4| + |x_4 - x_1|$. By considering all possible orderings (of which there are 4, namely: which of $\{x_1, x_2\}$ is more positive $\times$ which of $\{x_3, x_4\}$ is more negative), it is easy to show that $X = 2 (\max(x_1, x_2) - \min(x_3, x_4)) \le 4$.
Similarly, $Y = |y_1 - y_2| + |y_2 - y_3| + |y_3 - y_4| + |y_4 - y_1| = 2 (\max(y_1, y_4) - \min(y_2, y_3)) \le 4$.
The $1$-norm distance, aka Manhattan distance, between two points is defined as $m(p_i, p_j) = |x_i - x_j| + |y_i - y_j|$. Combining this with $X, Y$ we have:
$X + Y = m(p_1, p_2) + m(p_2, p_3) + m(p_3, p_4) + m(p_4, p_1) \le 8$
This implies we have at least one pair s.t. $m(p_i,p_j) \le 2$. Finally, triangle inequality ensures that the Euclidean ($2$-norm) distance $\le$ Manhattan distance, completely the contradiction.
The minimum number $\mathcal{N}$ is $4$.
It is very easy to show $\mathcal{N} \le 5$. Just divide the square into four squares of side $1$. If you pick $5$ points from the big square, one of the small squares will contain more than one points. The distances among the points in that small square will be no more than $\sqrt{2}$.
$\require{cancel}\cancel{\color{gray}{\text{I don't know any elegant proof for }\mathcal{N} \le 4}}$. Following is my first attempt of a proof of $\mathcal{N} \le 4$. It mimic the approach found in a paper by J.Schaer ${}^{\color{blue}{[1]}}$.
Let $[4] = \{1,2,3,4\}$.
WOLOG, choose a coordinate system so that the square is $S = [-1,1]^2$.
If $\mathcal{N} > 4$, we can choose $x_1, x_2, x_3, x_4 \in S$ such that $|x_i - x_j| > 2$ whenever $i,j \in [4]$ and $i \ne j$.
For any $u \in [0,2)$, let $U_k, k \in [4]$ be following 4 squares. $$\begin{array}{ll} U_1(u) = [-1,-1+u]^2,& U_2(u) = [1-u,1] \times [-1,-1+u],\\ U_3(u) = [1-u,1]^2, & U_4(u) = [-1,-1+u]\times[1-u,1] \end{array}$$
It is clear $S = \bigcup_{i\in[4]} U_i(\sqrt{2})$. Since the diameter of $U_i(\sqrt{2})$ is $2$, if any $U_i$ contains more than one points, say $x_j$ and $x_k$, then $|x_j - x_k| \le 2$. Contradict with our choice of $x_j$ and $x_k$.
From this, we can deduce $x_1, x_2, x_3, x_4 \in \bigcup_{i\in[4]} U_i(2-\sqrt{2})$. Furthermore, each square contains exactly one of the points. Relabeling $x_k$ if necessary, we can assume $x_k \in U_k(2-\sqrt{2})$ for $k \in [4]$.
For any $u \in (0,1)$, let $\mathcal{S}(u)$ be the statement $$\mathcal{S}(u) \stackrel{def}{=} x_k \in U_k(u), \forall k \in [4]$$
For any $u$ that $\mathcal{S}(u)$ is true, let $v = 2 - \sqrt{4-u^2}$ and consider following two rectangles $$[-1,1-v] \times [-1,-1+u] \supset U_1(u)\quad\text{ and }\quad [1-u,1] \times [+1+v,1] \supset U_3(u)$$ Both rectangles have diameter $2$. Since the first rectangle contains $x_1$ while the second rectangle contains $x_3$, none of them contains $x_2$. This implies $x_2 \in U_2(v)$. Apply similar arguments to other points, we obtain $x_k \in U_k(v)$ for $k = 1,3,4$ too. To summarize, we have shown
$$\mathcal{S}(u)\quad\implies\quad\mathcal{S}(2 - \sqrt{4 - u^2})$$
Construct a sequence $u_n$ by $$u_n = \begin{cases} 2-\sqrt{2},& n = 0\\ 2 - \sqrt{4-u_{n-1}^2}, & n > 0 \end{cases}$$ Since $\mathcal{S}(u_0)$ is true, $\mathcal{S}(u_n)$ is true for all $n$. Since $\lim_{n\to\infty} u_n = 0$, this leads to
$$x_k \in \bigcap_{n=0}^\infty U_k(u_n) = U_k(0), \forall k \in [4]$$
This means $x_1, x_2, x_3, x_4$ are the four vertices of $S$. In particular, $x_1 = (-1,-1)$ and $x_2 = (1,-1)$ and $|x_1 - x_2| = 2$. This contradicts with our choice of $x_1, x_2$.
Our original assumption $\mathcal{N} > 4$ cannot be true and hence $\mathcal{N} \le 4$.
Since it is trivial to find $3$ points in $S$ at a distance $> 2$ apart, we have $\mathcal{N} > 3$. As a result, the minimum number $\mathcal{N}$ is $4$.
Update
I figure out a simpler argument for $\mathcal{N} \le 4$.
Once again, let say we have $x_1,x_2,x_3,x_4 \in S$ with $|x_i - x_j| > 2$ whenever $i \ne j$. Since the circle centered at origin $O$ with radius $2$ completely cover $S$. If any one of $x_k$ is $O$, there will be no more room for other three points.
This means none of $x_k$ is $O$. If $(r_k,\theta_k)$ is the polar coordinates for $x_k$, $\theta_k$ will be well defined (up to multiples of $2\pi$). It is clear we can pick a pair whose "$\theta$" is at most $\frac{\pi}{2}$ apart. Rotating/Reflecting the square and relabeling $x_k$ is necessary, we can assume
$$\theta_1 \in [0,\frac{\pi}{4} ),\; \theta_2 \in [\theta_1,\theta_1 + \frac{\pi}{2}]\quad\implies\quad x_1, x_2 \in \bigg\{ p \in S : \theta_1 \le \theta(p) \le \theta_1 + \frac{\pi}{2} \bigg\}$$ Notice the set on RHS has diameter $\frac{\sqrt{2}}{\cos\theta_1} \le 2$. This forces $|x_1 - x_2| \le 2$ and contradicts with our choices of $x_1, x_2$.
References