Points in plane with every pair having at least two equidistant points? I was given this question in person by a fellow trainee at the downtime of an IMO training session, which made me think this problem is Olympiad related. I am interested in the solution as much as the origin!

$\textbf{Problem:}$Does there exist a non-empty finite set of points $P$ in $\mathbb{R}^2$ such that for each pair of points $x$, $y$ in $P$ there exists at least two distinct points $a$ and $b$ in $P$ such that both $a$ and $b$ are equidistant from $x$ and $y$.

To be honest, in over a decade and getting a degree in Mathematics, I have not made much headway into this problem. I tried to do some counting based on the number of pairs and pigeonhole to get the conclusion that there must be a point that is the circumcenter of a triangle made up of points in $P$. Assuming $P$ is a minimal solution (in terms of size of $P$) does not seem to help that much.
EDIT: originally the question left open whether it was in the plane or space, but the space case is trivial.
EDIT EDIT: added a note to say the set should be non-empty. Note that we do not need at least two points, because when we say &quot;pairs of points&quot; we don't say &quot;distinct pair of points&quot;!
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 &quot;fora&quot;), 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...
Let $P$ be the finite set of points above mentioned.
We have, by definition, that for every pair of points $x$ and $y$, there is another different pair $a$ and $b$ that are located in the line that passes through the midpoint of $x$ and $y$ and is perpendicular to the line segment $\overline{\rm xy}$ connecting such points.
Let $L$ be the set of all lines that can be constructed by passing through each pair of points in $P$ (this is a much bigger set, but still finite). Now consider the pair of lines $l_1,l_2\in L$ which present the smallest nonzero angle between them (there can be more than one, but it's enough to consider one pair). Then there is a pair of points $x_1\in l_1$ and $x_2\in l_2$ which doesn't satisfy the condition, i.e., there is no other pair $a,b$ equidistant from $x_1$ and $x_2$, which leads to a contradiction.
Note that if such pair $a,b$ existed, the condition &quot;$l_1$ and $l_2$ having the smallest nonzero angle between them&quot; would not hold, as the angle between $l_1$ or $l_2$ and the line perpendicular to the segment $\overline{\rm x_1x_2}$ (the line passing through $a$ and $b$) would be smaller.
Therefore, $P$ and $L$ must be both infinite sets.