1
$\begingroup$

There are $2n$ points on a circle. The distance (defined by shortest distance you would take to walk from one point to another along the circle) between adjacent points are the same. $n$ points are black and $n$ points are white.

Now we compute the pairwise distances between all the black points and pairwise distances between all the white points. Prove they have the same collection ( with multiplicities) of pairwise distances.

It looks like there has to be a simple trick to map from one group of points to the other through some reflection principle. But I haven't figured out a way...

$\endgroup$
1
  • $\begingroup$ I am facing a similar problem. Do you know where this problem come from ? Or where can I get similar variations? $\endgroup$
    – arbolverde
    Commented Oct 19, 2022 at 16:12

2 Answers 2

Reset to default
3
$\begingroup$

consider the set of all pairwise distance of black, if distance $j$ is not in it, then $x \mapsto x+j$ is a bijection between black and white.

If we take multiplicity into consideration, the multiplicity of black $j$ is number of points that itself is black and maps to black, it is the same as # of points that is white and maps to white.

$\endgroup$
10
  • $\begingroup$ How exactly do you see that? $\endgroup$
    – R.Yeh
    Commented Oct 2, 2020 at 1:07
  • $\begingroup$ @R.Yeh Since the points are equally spaced around the circle, for any fixed $k$ the map $x \mapsto x+k$ [mod $2n$] is a bijection. And if no pairwise distance is $k$ then any black maps to a white (and conversely). $\endgroup$
    – coffeemath
    Commented Oct 2, 2020 at 3:46
  • $\begingroup$ Okay, but what if ... all the pairwise distances are present between black points? E.g. regular octagon $A_1A_2\cdots A_8$ where points $A_1,A_2,A_3$ and $A_6$ are black and the rest are white? $\endgroup$
    – user700480
    Commented Oct 2, 2020 at 11:11
  • $\begingroup$ @StinkingBishop: In that case consider the pairwise distances of white: either they include all possible distances, or you can use a missing one to get a bijection between white and black. $\endgroup$
    – Brian M. Scott
    Commented Oct 2, 2020 at 19:04
  • 2
    $\begingroup$ @StinkingBishop that is my intention though.. with multiplicities. let me edit my original post.. $\endgroup$
    – R.Yeh
    Commented Oct 4, 2020 at 2:08
1
$\begingroup$

(Fill in any gaps yourself.)

Step 1: Consider any ring comprising of B's and W's (with possibly an unequal number of them).

Show that the number of $BW$ (in that order) is equal to the number of $WB$.

Show that the number of $BB$ is equal to the number of $B$ minus the number of $BW$.

Step 2: Given the setup, fix $d$. Then, construct a ring of $B$ and $W$ by taking point 1, going around distance $d$ till we loop back.
If there are leftover points (when $\gcd(d,2n)\ne 1$), then take another starting point to form multiple loops.

Step 3: For the (possibly multiple) loops corresponding to $d$, each individual loop has the same number of BW and WB. The total across all these loops have $n$ $B$'s and $n$ $W$'s.

Show that the total number of $BB$ and $WW$ are equal.

Hence conclude that in the setup, the number of distances of length $d$ are equal.

Hence, the multi-set of distances are equal.

$\endgroup$
1
  • $\begingroup$ I am facing a similar problem. Do you know where this problem come from ? Or where can I get similar variations? $\endgroup$
    – arbolverde
    Commented Oct 25, 2022 at 23:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .