Same trick goes for IMO 99 .

Solution found in collaboration with proglote. Let $G = \frac{X_1 + ... + X_n}{n}$, where a letter denotes the vector which represents the point. Let $G$ be the origin. Now, remark that we have $(X_i - X_k) \bullet (X_i - X_k) = (X_j - X_{\sigma(k)}) \bullet (X_j - X_{\sigma(k)})$. Summing over all $k$ we get \[n X_i^2 - 2X_i \sum_{k=1}^n X_k + \sum_{k=1}^n X_k^2 = n X_j^2 - 2X_j \sum_{k=1}^n X_{\sigma(k)} + \sum_{k=1}^n X__{\sigma(k)}^2\] Using the fact $\sigma$ is a permutation and that $G = 0$, we get: \[nX_i^2 = nX_j^2 \implies d(G,X_i) = d(G,X_j)\] Thus the $n$ points lie on a circle centered at their average. Remark that we have the multiset of distances from a specific point to other points is the same across all points. Now take a point $X$ and suppose $X_i, X_j$ are the two closest points to it. Then note that if $d(X,X_i) = d(X,X_j)$ we have a regular $n$-gon by considering the point not $X$ next to $X_1$ with distance $d(X,X_i)$ from it and then repeating, noting that every point must be generated by this using the minimality of the distance assumption and that the process must eventually loop back to $X$ due to the points being concyclic. It is clear by letting the permutation just be a shift function by $j-i$ that this works (where we first apply a permutation to make the points labelled $X_1,X_2,...,X_n$ is clockwise order). Now, suppose $d(X,X_i) < d(X,X_j)$. By using the multiset statement it is clear that $X_i, X_j$ must lie on different sides of $XG$ as otherwise $d(X_i, X_j) < \max(d(X,X_i), d(X,X_j))$ which contradicts their minimality as this distance must exist from a point and $X$. But then applying a similar argument as above (except we alternate finding points of distance $d(X,X_i)$ and $d(X,X_j)$) we find the $n$ points must determine a polygon whose sides alternate in size, i.e. every other side is equal in size. It it clear this configuration works by considering a shift function if the two points are an even number of vertices away, while if they are an odd number by first performing a reflection with respect to $X_jG$ (note that $n$ must be even so this is valid) and then doing a shift by $j-i$ if they are an odd number of vertices away.

I have solution with no computations. Let a,b,c,d denote the 1st, 2nd, 3rd smallest lengths and the largest length, respectively First we prove the points are polygon. If not, take convex hull and point inside it, P. Let PQ=d. Then let R be region of intersection of circle center P radius d and circle center Q radius D. All points lie inside R and so if we draw tangent line through P to R, all points will be on same side of this line, so P isn't inside convex hull, contradiction. Now I prove following lemma. Lemma: if ABC is triangle and D any point such that ACBD is convex, if AB<BC then AD<DC. Proof: Take R to be region defined by segment AB, ray CB beyond B and ray CA beyond A. So D is in R. Take R' to be region defined by halfplane of the perpendicular bisector of CA not containing B. Is easy to see R and R' have no intersection, and so if D is in R, D isn't in R', so AD<DC. Now take segment AB of length a. If AB is not a side of the polygon, take C and D on opposite sides of AB such that AD=d and we get contradiction by lemma. Therefore all segments of length a are sides. Case 1: n odd We conclude that all the sides of polygon are length a. Take segment AB of length b, and suppose it is not a diagonal which is 2 "sides" wide. With help of lemma, take C and D on opposite sides of AB such that AD=d and BC is not length a, and we get contradiction. Therefore all diagonals of 2-sides-wide measure b, and all b-segments are diagonals like these. Then all angles of polygon are equal (because if ABC are consecutive vertices, AB=BC=a and CA=b so angle ABC is fixed) and then it is regular polygon, done Case 2, n even If all sides measure a, we finish as above. So assume not. Analogously we can prove all segments of length b are sides of polygon. so polygon alternates sides: a,b,a,b, etc. Using same idea as above with a segment of length c, we see that all diagonals that are 2-sides-wide are of length c, so we finish with same idea. The result is a polygon with all angles equal and sides alternating in length. We are done. Answer: take any real a,b. Then the points form an equiangular polygon with sides of length a,b,a,b,etc...

Beautiful result! RMM 2011/5 wrote: For every $n\geq 3$, determine all the configurations of $n$ distinct points $X_1,X_2,\ldots,X_n$ in the plane, with the property that for any pair of distinct points $X_i$, $X_j$ there exists a permutation $\sigma$ of the integers $\{1,\ldots,n\}$, such that $\textrm{d}(X_i,X_k) = \textrm{d}(X_j,X_{\sigma(k)})$ for all $1\leq k \leq n$. (We write $\textrm{d}(X,Y)$ to denote the distance between points $X$ and $Y$.) (United Kingdom) Luke Betts Answer: For $n$ odd, the only valid set is the vertex set of a regular $n$-gon; for $n$ even, it is the vertex set of a cyclic $n$-gon with equal alternating sides. Note that these sets do indeed satisfy the desired property. It remains to show that these are the only such sets. Let $G$ be the center of mass for the set of points $\{X_1, \dots, X_n\}$. Claim: For any $n \ge 3$, all the vertices lie on a circle centered at $G$ (henceforth, $\omega$). (Proof) Note that for any point $P$ in the plane, we know that $$\sum^n_{i=1} |PX_i|^2 = n|PG|^2+\frac{1}{n} \sum_{1 \le i \le j \le n} |X_iX_j|^2.$$This can easily be seen to hold by expanding both sides as sums of dot products. Now, we remark here that for $P \in \{X_1, \dots, X_n \}$ our condition tells us that the LHS is invariant. However, RHS implies $|GX_i|$ is the same for all $i$; validating the claim. $\blacksquare$ WLOG, $n \ge 5$ as the cases $n \in \{3, 4\}$ are easy to see. Re-label the vertices as $A_1, \dots, A_n$ in counter-clockwise sense. Call all chords $A_iA_{i+2}$ (indices mod $n$) nice. Claim: All nice chords have the same length. (Proof) By suitable rotation, we may assume that $A_1A_3$ has the minimal length amongst all nice chords. We begin by noting that $|A_1A_3| \ne |A_1A_2|$. Otherwise, we have $$\measuredangle A_1A_{n-1}A_3>90^{\circ} \implies |A_1A_3|>|A_1A_{n-1}|,$$which contradicts the minimality condition. Note that this property holds for all minimal nice chords and we can replicate the exact same argument. Now, by our condition, there exists a point $P$ on this circle so that $|PA_3|=|A_1A_2|$. Clearly, $P \ne A_1, A_2, A_3$ and $P$ cannot lie on the arc $A_1A_2A_3$. Evidently, $|A_1A_3|=|PA_2| \implies P \in \{A_n, A_4\}$ depending on whether $A_2$ is closer to $A_1$ or $A_3$, respectively. However, we can repeat this argument since either $|A_2A_4|$ or $|A_2A_n|$ is a minimal nice chord; and it is clear that the subsequent point does lie in cyclic order of vertices. Therefore, all nice chords have equal lengths. Consequently, all alternating chords are also equal. $\blacksquare$ It is easy to see that this means the polygon is regular for $n$ odd and has equal alternating sides for $n$ even, i.e., it is a union of two-vertex disjoint equal sided regular polygons inscribed in the same circle. $\blacksquare$

The answer is when $\{X_1,\ldots,X_n\}$ form the vertices of some convex cyclic $n$-gon whose sides alternate in length. Note that for $n$ odd this forces the $n$-gon to be regular. The condition implies that for any $i,j$, the multisets $\{X_iX_k\}_k$ and $\{X_jX_k\}_k$ are the same, i.e. $\{X_iX_k\}_k$ is the same across all $i$. Let $G$ be the centroid of the points. By the parallel axis theorem, we have $$\sum_{k=1}^n X_iX_k^2=nGX_i^2+\sum_{k=1}^n GX_k^2,$$hence $GX_i$ is constant across all $i$, i.e. the $X_i$ all lie on a circle (centered at $G$, but this doesn't matter). Now WLOG relabel the points such that $X_1X_2\ldots X_n$ is convex and let its circumcenter be $\Omega$. First note that $X_1\ldots X_n$ must contain the center of $\Omega$, else the edge closest to the center must be strictly longer than any other distances between points, which is forbidden. Now consider the shortest edge in $X_1\ldots X_n$ and WLOG suppose that it is $X_1X_2$. Because $X_1\ldots X_n$ contains its circumcenter, for any $i \neq j$ we have $X_iX_j \geq \min\{X_iX_{i-1},X_iX_{i+1}\}$ since $X_j$ doesn't lie on arc $X_{i-1}X_iX_{i+1}$. Thus for each $i$ we must have $X_1X_2 \in \{X_iX_{i-1},X_iX_{i+1}\}$. Moreover, if some $i$ has $X_iX_{i-1}=X_iX_{i+1}=X_1X_2$, then from a similar argument to the above we force $X_jX_{j-1}=X_jX_{j+1}=X_1X_2$ for all $j$, so for $n$ odd we clearly force all sides to be equal. For $n$ even, this is also forced unless we precisely have $X_1X_2=X_3X_4=\cdots=X_{n-1}X_n$. In this case, WLOG let $X_0X_1$ be the smallest edge longer than $X_1X_2$. Note that the arc $X_0X_1$ not containing any other vertices should have measure less than $180^\circ$. Then for each even $i$ we should have $X_iX_k=X_0X_1$ for some $k \neq i+1$ (since $X_iX_{i+1}=X_1X_2$ already), but if $k \neq i-1$ we get a contradiction, since if minor arc $X_iX_k$ contains $X_{i+1}$ but has measure at most that of $X_0X_1$ then $X_{i+1}X_{i+2} \leq X_{i+1}X_k<X_iX_k=X_0X_1$, and having minor arc $X_iX_k$ contain $X_{i-1}$ is similarly absurd. This implies that $X_0X_1=X_2X_3=\cdots$, hence $X_1\ldots X_n$ should have alternating sides as desired. $\blacksquare$