combinatoricsrectangles
I need help to answer the following question:
Is it possible to place 26 points inside a rectangle that is $20\, cm$ by
$15\,cm$ so that the distance between every pair of points is greater
than $5\, cm$?
I haven't learned any mathematical ways to find a solution; whether it maybe yes or no, to a problem like this so it would be very helpful if you could help me with this question.
Let $G$ denote the graph on the $n$ vertices, where two vertices share an edge if and only if the distance between them is $d$. Let $k$ denote the number of edges in $G$. We wish to show that $k\leq n$.
Let $G'$ denote the graph obtained by repeatedly removing all vertices $v\in G$ with $\deg v\leq1$, so that the number of edges removed is no greater than the number of vertices removed. Then it suffices to show that $k'\leq n'$, where $n'$ and $k'$ denote the numbers of vertices and edges of $G'$, respectively.
Suppose toward a contradiction that $\deg v\geq3$ for some $v\in G'$. The pairwise distance between the neighbours of $v$ is also at most $d$, and hence all neighbours of $v$ lie on a circular arc of radius $d$ centered at $v$ of at most $\tfrac\pi3$ radians. Let $w_1,w_2\in G'$ be the two neighbours of $v$ that are furthest apart, and $w\in G'$ any other neighbour of $v$. The following image clarifies the situation:
The four circles are centered at $v$, $w_1$, $w_2$ and $w$ and all have the same radius $d$. It follows that all other vertices of $G'$ are contained in the region shaded red. In particular the only vertex in $G'$ at distance $d$ from $w$ is $v$. But then in $G'$ we have $\deg w=1$, a contradiction. This shows that $\deg v=2$ for all $v\in G$ and hence that $k'\leq n'$.
A picture is worth a thousand words:
... but I will write a few words, nevertheless. This configuration has many symmetries and interesting properties, some of which I will describe here; however, I recommend trying to explore the configuration and figure them out on your own before reading further.
The eight points are arranged in two squares of different side lengths, with the same centre, and at a 45 degree angle from each other, the internal square coloured red and the external coloured blue. There are also eight equilateral triangles with vertices from the eight points: each side of the internal red square is completed to an outward-pointing equilateral red triangle, and each side of the external blue square is completed to an inward-pointing blue triangle.
All twelve red segments have equal lengths, as do all twelve blue segments. These equalities suffice to verify that any pair of points has a pair of two equidistant points. Up to symmetries, there are only six cases to check: two where both vertices are from the blue square (adjacent or opposite); two where both vertices are from the red square (adjacent or opposite); and two where each vertex is from a different square (and the distance between the two vertices is either red or blue). The final two cases are the nicest and most interesting, and the latter of which is shown in the diagram, where the green perpendicular bisector of the two green points passes through a different pair of points, obtained from the first pair by a 90 degree rotation.
I do not know the origin of the problem, but I have encountered it before—on the xkcd forums (or "fora"), of all places, at least 10, maybe 15 years ago. I had recently recalled this problem and had presented it to some of our IMO students. My attempt to look up the original formulation and my original answer led me here. Sadly, the xkcd fora seem to have been offline since August 2019, and apparently they were not archived in full (or at least, I am unable to find such an archive), and thus some small pages in the history of this question might now be forever lost...
Best Answer
No, it is not. If we assume that $P_1,P_2,\ldots,P_{26}$ are $26$ distinct points inside the given rectangle, such that $d(P_i,P_j)\geq 5\,cm$ for any $i\neq j$, we may consider $\Gamma_1,\Gamma_2,\ldots,\Gamma_{26}$ as the circles centered at $P_1,P_2,\ldots,P_{26}$ with radius $2.5\,cm$. We have that such circles are disjoint and fit inside a $25\,cm \times 20\,cm$ rectangle. That is impossible, since the total area of $\Gamma_1,\Gamma_2,\ldots,\Gamma_{26}$ exceeds $500\,cm^2$.
Highly non-trivial improvement: it is impossible to fit $25$ points inside a $20\,cm\times 15\,cm$ in such a way that distinct points are separated by a distance $\geq 5\,cm$.
Proof: the original rectangle can be covered by $24$ hexagons with diameter $(5-\varepsilon)\,cm$. Assuming is it possible to place $25$ points according to the given constraints, by the pigeonhole principle / Dirichlet's box principle at least two distinct points inside the rectangle lie in the same hexagon, so they have a distance $\leq (5-\varepsilon)\,cm$, contradiction.
Further improvement:
the depicted partitioning of a $15\,cm\times 20\,cm$ rectangle $R$ in $22$ parts with diameter $(5-\varepsilon)\,cm$ proves that we may fit at most $\color{red}{22}$ points in $R$ in such a way that they are $\geq 5\,cm$ from each other.