Sets of vertices distances

Question

Let there be a regular 2n-gon, $n \ge 2$. Two disjoint set of vertices are chosen, each containing n elements. All the distances between the points in each set are recorded, and then placed in order form shortest to largest (multiple lengths are recorded multiple times.) Prove that the sequence corresponding to each set will be identical.

I proved that each distance appears 2n times, and I tried a pigeonhole argument, by I have had no success.

---

*I reposted since there were a couple of things wrong, and I deleted the original post.

Answer 1

I think one way to do this is with an invariant argument. First, some terminology. Let's say we color $n$ vertices red and the other $n$ blue. For $d=1,2,\dots,n$ say that two vertices are $d$-neighbors if they are $d$ vertices apart, so that $1$-neighbors are adjacent, and $n$-neighbors are opposite. Then the claim of the theorem is there are the same number of pairs $d$-neighbors in $R$ as in $B$, for $d=1,\dots,n.$ Call a coloring $(R,B)$ balanced if the contention of the theorem holds for this coloring.

Start by coloring $n$ consecutive vertices red, and the remainder blue. Since $R$ and $B$ are congruent, the the coloring is clearly balanced. Now I claim that if we start with a balanced coloring, and recolor one red vertex blue and one blue vertex red, the new coloring will be balanced. This will prove the theorem, since we can arrive at any coloring by starting with the base coloring, and switching red-blue pairs.

For $d=1,2,\dots,n-1$ each vertex has $2$ $d$-neighbors, and each vertex has $1$ $n$-neighbor. First consider $d<n$. Suppose vertex $r$ is colored red, vertex $b$ is colored blue, and we recolor them to arrive at a new coloring $(R',B')$. First consider the case where $r$ and $b$ are not $d$-neighbors. If $r$ has $2$ red $d$-neighbors in $(R,B)$ coloring $r$ blue will reduce the number of red $d$-neighbor pairs by $2$ and will not affect the number of blue $d$-neighbor pairs. If $r$ has $0$ red $d$-neighbors in $(R,B)$ coloring $r$ blue will increase the number of blue $d$-neighbor pairs by $2$ and will not affect the number of red $d$-neighbor pairs. If $r$ has exactly one red $d$-neighbor, then recoloring $r$ blue will reduce the number of red $d$-neighbor pairs by $1$ and increase the number of blue $d$-number pairs by $1$. Similar statements hold for the effect of recoloring $b$ red.

It is clear that if $r$ has the same number of red $d$-neighbors as $b$ has blue neighbors, then $(R',B')$ will be balanced. We need to check the cases where the numbers are different. By symmetry, we may assume that $r$ has more like-colored neighbors that does $b$.

Suppose $r$ has $2$ red neighbors and $b$ has no blue neighbors. Recoloring $r$ decreases the number of red $d$-number pairs by $2$ and doesn't affect the number of blue $d$-neighbor pairs. Recoloring $b$ red increases the number of red $d$-number pair by $2$, and doesn't affect the number of blue $d$-neighbor pairs, so the net effect is to change nothing.

Suppose $r$ has $2$ red neighbors and $b$ has $1$ blue neighbor. As above, recoloring $r$ reduces the number of red $d$-neighbor pairs by $2$ and doesn't affect the number of blue $d$-neighbor pairs. Recoloring $b$ red reduces the number of blue pairs by $1$ and increases the number of red pairs by $1$ and so both numbers decrease by $1$.

I leave the remaining cases to you. You still have to deal with the case where $r$ has $1$ red neighbor and $b$ has no blue neighbor, the cases where $r$ and $b$ are $d$-neighbors, and the case where $d=n$.

Full disclosure: I haven't carried out these steps, but they must be true if the theorem is, and in that case they should be easy, as above.

Answer 2

Partial Answer

From a matrix point of view, we can arrange the distances as sketched below for the case of an octagon.

We can see that the matrix rows are a cyclic shift of the first row, and same for the columns.
It has a gamut of symmetries which I am unable to fix in standard terms.

It seems true that symmetry is preserved when the same permutation is done on the rows and the columns.

Answer 3

First observe that the graph theory notion of distance, where the distance between two vertices is defined as the number of edges in the shortest path joining them, is equivalent to Euclidean distance as far as this problem is concerned.

Consider a regular $m$-gon with $b$ blue vertices and $y$ yellow vertices so that $b+y=m$. Number the vertices $0$, $1$, ..., $m-1$ and consider the following sets of ordered pairs of vertices with (graph-theoretic) separation $d$, \begin{align} B_d&=\{(j,j+d)\mid 0\le j\le m-1\text{ and vertices $j$ and $j+d$ are both blue}\},\\ Y_d&=\{(j,j+d)\mid 0\le j\le m-1\text{ and vertices $j$ and $j+d$ are both yellow}\},\\ C_d&=\{(j,j+d)\mid 0\le j\le m-1\text{ and vertex $j$ is blue and vertex $j+d$ is yellow}\},\\ D_d&=\{(j,j+d)\mid 0\le j\le m-1\text{ and vertex $j$ is yellow and vertex $j+d$ is blue}\}, \end{align} where $j+d$ is computed modulo $m$. Clearly $\lvert B_d\rvert+\lvert C_d\rvert=\lvert B_d\rvert+\lvert D_d\rvert=b$ and $\lvert Y_d\rvert+\lvert D_d\rvert=\lvert Y_d\rvert+\lvert C_d\rvert=y$. It follows that $\lvert C_d\rvert=\lvert D_d\rvert$. If $y=b$, it also follows that $\lvert B_d\rvert=\lvert Y_d\rvert$.