Points On The Plane, Are Scarier Than Snakes

We know that the maximum distance between two pints in a square is along it's diagonal.So for the constraints given in the problem to hold it is essential that the given points should lie inside a square of side length $\sqrt{2}$ and diagonal length = $2$ .

$\textbf{1.}$ Let us first partition this square into 4 parts as show in the figure img So from this figure it is evident that there can be at most 4 points such that the pairwise distance between each of them is is at least $\sqrt{2}$ .This clearly follows from the pigeonhole principle.

$\textbf{2.}$ If such a construction is possible then since the distance between any 2 sides is $\sqrt{2}$ we must have a construction like this figure : img

where $x$ and $\sqrt{2}-x$ is taken as shown. By the Pythogorean theorem we have $x^{2}+(\sqrt{2}-x)^{2} = 2$ $2x^{2}+2-2\sqrt{2}x = 2$ $2x^{2}-2\sqrt{2}x = 0$ $x = \sqrt(2)$ or $x =0$ . According to our case the distance between the points should be greater than $sqrt{2}$ so 4 points cannot be obtained. SO at most 3 points can be put in the region with pairwise distance > $\sqrt{2}$ .

Such a construction is easily possible by taking the points as close to the vertices as possible.

$\textbf{3.}$ Now we can choose the other 3 points as close as possible(infinitesimally close-how about that??) to the initial 3 points in which case we will again have another triplet of points such that their pairwise distance is strictly greater than $\sqrt{2}$ .

img

So clearly from the diagram it is evident that only 3 pairs of points have distance < $\sqrt{2}$ and hence this is optimal.

The total number of pairs of points = 15.

So the greatest number pairs of points having distance > $\sqrt{2}$ is $\boxed{12}$ .

We will approach this problem using the following lemmas:

Lemma 1: Given 4 points on the plane, let the maximum distance between 2 points be $M$ and the minimum distance between 2 points be $m$ , then $\frac {M}{m} \geq \sqrt{2}$ .

Lemma 2: Given a graph with 6 vertices which are connected by 13 edges, there must be a complete graph on 4 vertices.

Then, given these lemmas, for the original set of 6 points, draw an edge in if the length is more than $\sqrt{2}$ . If there are at least 13 edges, then by Lemma 2, there exist 4 points each of which are distance $\sqrt{2}$ apart. By Lemma 1, the maximal distance would be greater than $\sqrt{2} \times \sqrt{2} = 2$ , which contradicts the assumptions. Hence, there are at most 12 such pairs.

It remains to show that 12 is possible. Let $ABC$ be an equilateral triangle of edge length 2. Take $A_1, B_1, C_1$ just within the triangle, and close to the respective vertices. This gives us $3 \times 4 \times 2 \div 2 = 12$ edges with length close to 2. Hence we are done.

---

Proof of Lemma 1: We break into cases depending on the number of points in the convex hull.

If the convex hull consists of 2 points, then we have a straight line. The shortest distance is hence at most $\frac{1}{3}$ of the longest distance (the entire line).

If the convex hull consist of 3 points, then we can show that $\frac {M}{m} \geq \sqrt{3}$ . Let $O$ be the point contained within the convex hull. Then we can find a triangle where $\angle AOB \geq 120 ^ \circ$ . WLOG, let $OA \geq OB$ , so $\angle OAB \leq 30^\circ$ . Then $\frac {AB}{OB} = \frac {\sin \angle AOB} {\sin \angle OAB} \geq \frac{ \sin (2 \angle OAB)}{\sin \angle OAB} \geq 2 \cos \angle OAB \geq 2 \cdot \frac {\sqrt{3} }{2} = \sqrt{3}$ .

If the convex hull consists of 4 points, then one of the angles is at least $90 ^ \circ$ . Let it be $\angle ABC$ . Let $AB \geq BC$ , so $\angle BAC \leq 45 ^ \circ$ . Then, $\frac {AC} {BC} = \frac { \sin \angle ABC} {\sin \angle BAC} \geq \frac { \sin ( 2\angle BAC)} { \sin \angle BAC} = 2 \cos \angle BAC \geq 2 \cos 45^\circ = \sqrt{2}$ .

Proof of Lemma 2: Since there are at most ${6 \choose 2} = 15$ edges, there are 2 edges that are not connected. If these 2 edges share a common vertex V, then any 4 of the other points will work. If the 2 edges do not share a common vertex, take 1 vertex from each of these pairs, and the other 2 vertices.