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 "pairs of points" we don't say "distinct pair of points"!
 A: Before I begin, a bit of philosophy on this problem:
I sincerely think there is no such set. I tried some onfigurations and I cannot seem to find one that works. So from now on, I will just talk about disproving the problem
This problem is clearly a geometric-combitoric style question. As far as I see, I don't think the geometric part of the problem is very important; I think only the simple notions of perpendicular bisectors and maybe polygons is enough. The important part is the combinatorical part and here are the main ideas that come in mind:

*

*extremal principle

*pigeonhole principle

*double countings of any useful thing (angles, triangles, edges etc.)

*considering a graph or the set of lines which pass through (at least) $2$ points or maybe the set of perpendicular bisectors of the set of segments

However, here is the big big issue:
We were never told that the points cannot be collinear or form parralel lines
As a bit of theory, we say that some points are in general position when no $3$ are collinear and no $2$ lines formed by points from our set are parralel. So we were never told that the set of points we are looking for is a general position! This means that we cannot use most of the ideas listed above as counterexamples are easy to find.
And yet is seems so easy.
I have tried myself various applications of the extremal principle and double countings but didnt actually manage to get a contradiction. However, I did manage to get a contradiction assuming that the points are in general position! So here is the solution:

Let $P$ be the set of points. Let $S$ be the set of lines that pass through exactly $2$ points of $P$. Observe that $|S|=\binom{n}{2}$ because the points are in general position.
Consider $S'$ the set of the perpendicular bisectors of the segments whose endpoints are in $P$. Because there are $\binom{n}{2}$ segments whose endpoints are in $P$ and the points are in general position, there are $\binom{n}{2}$ perpendicular bisectors, so $|S'|=\binom{n}{2}$.
BUT, for any segment $AB$ there are at least $2$ points $X,Y$ which both lie on the perpendicular bisector of the segment, thus every perpendicular bisector in $S'$ is actually one of the lines in $S$, so there exists an injection from $S'$ to $S$.
But we have shown that $|S|=|S'|$, so there must be a bijection from $S'$ to $S$, so every line that passes through $2$ points from $P$ is the perpendicular bisector of a segment whose endpoints are in $P$.
Take the convex hull of the points in $P$ and take any line formed by $2$ points on the convex hull. That line clearly cannot be the perpendicular bisector of a segment whose endpoints are in $P$
$\mathcal{Q.E.D}$

The fact that the points are in general position let us prove that there is an injection from $S'$ to $S$. If the points can actually be collinear or form parralel lines, then the above argument is false.

To conclude, there is no such set assuming the points are in general position. As for the general case, I am not sure. To be honest, the original statement might involve this detail, and Cryvate might have forgotten to add it, because in my experience, $99\%$ of geometric-combinatorical problems involve points in general position.

EDIT: $2$ people have pointed out in the comments that the question did not involve general position.
Yes, I know, I simply wanted to show a solution for the case in which the points are indeed in general position and highlight why the problem is much harder when they are not.
I discussed some approcahes and this was purely theoretical on te main issue, while providing the solution for the special case.
Moreover, as I said above, it is highly possible that if this was at an olympiad preparation camp, the original question actually involved general position. I am myself an olympiad student and for all I know, $99\%$ of these problems involve a general position, and when they don't they usually involve osmething else, like colorings or supplementary conditions.
A: 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...
A: 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 "$l_1$ and $l_2$ having the smallest nonzero angle between them" 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.
