5
$\begingroup$

Consider the sequence $A_1,A_2,A_3, ..., A_{2n-2}, A_{2n-1}, A_{2n}$ of $2n$ points, spaced equally and clockwise on a circle.

For which $n \geq 2$ can you choose $n$ pairs of points $(A_i, A_j)$ such that every point is part of exactly one pair and every distance from $\{0,1, ..., n-1\}$ is covered by some pair $(A_i, A_j)$. A distance of a pair is defined by the smallest number of points that lie between $A_i$ and $A_j$.

For example, $n=4$ works: The sequence beeing $A_1, A_2, A_3, A_4, A_5, A_6, A_7, A_8$, we can choose pairs $(A_2, A_3), (A_6, A_8), (A_4, A_7), (A_1, A_5)$ with distances $0,1,2,3$ respectively, satisfying the condition.

$\endgroup$
3
  • $\begingroup$ it may have sth to do with graph coloring? $\endgroup$ Commented Aug 18, 2023 at 9:45
  • 2
    $\begingroup$ @C.C. The question can be phrased as: for what $n$ does a $(1,1)$-biregular graph with $n$ edges admit a graceful labeling? $\endgroup$ Commented Aug 18, 2023 at 10:33
  • $\begingroup$ You are using $n$ for two different things. You should change the letter used for the subindex of the pairs. $\endgroup$ Commented Aug 18, 2023 at 10:49

2 Answers 2

Reset to default
3
$\begingroup$

Thanks to @C.C. idea about a connection with graph theory, I have first searched about graceful labeling of graphs and found A Dynamic Survey of Graph Labeling by Joseph A. Gallian, and there, on section 2.5, "Disconnected Graphs", a reference to Skolem Sequence, which is exactly what you are looking for.

The 1957 paper On certain distributions of integers in pairs with given differences by Th. Skolem proves that a Skolem sequence of length $2n$ exists if and only if $n \equiv 0,1 \pmod 4$.

Here I report the proof that no sequence can exist with $n \equiv 2,3 \pmod 4$. Proving that a sequence always exists for $n \equiv 0,1 \pmod 4$ is longer (see the article).

Let $(a_k,b_k)$, $k=1,\ldots,n$ be the chosen couples in $(1,2,\ldots,2n)$ with $a_k \lt b_k$. Therefore:

$$\sum_{k=1}^n (b_k-a_k) = \sum_{k=1}^n k = \frac{n(n+1)}{2}$$

and:

$$\sum_{k=1}^n (b_k+a_k) = \sum_{k=1}^{2n} k = n(2n+1)$$

adding the two equations yields:

$$\sum_{k=1}^n b_k = \frac{n(5n+3)}{4}$$

which is an integer only when $n \equiv 0,1 \pmod 4$.

$\endgroup$
1
  • $\begingroup$ Thanks, great work! Beautiful how intertwined math is. $\endgroup$ Commented Aug 18, 2023 at 14:55
3
$\begingroup$

This is not a full answer but a long comment containing some experimental evidence for further analysis.

If I interpret the question correctly, the distance is measured clockwise, so everything is equivalent to considering the sequence of numbers $(1,2,\ldots,2n-1,2n)$ instead of a circle. Also, in the following, I will use distances computed as the plain difference between the two points in the couple, therefore leading to differences $1,2,\ldots,n$ rather than $0,1,\ldots,n-1$.

The problem can be modeled as a linear programming problem with binary variables, with variables $x_{i,j}, 1 \le i \lt j \le 2n$. $x_{i,j} = 1$ when the couple $(i,j)$ is chosen for the distance $j-i$, $x_{i,j} = 0$ otherwise.

The problem is then e.g. minimize $x_{2n-1,2n}$ subject to:

$$\sum_{k = i \space \lor \space k = j} x_{i,j} = 1, k=1,\ldots,2n$$

$$\sum_{k = j-i} x_{i,j} \ge 1, k=1,\ldots,n$$

I chose just a random objective function and also the second constraint could be replaced with an equality.

For example for $n=4$ we have:

Minimize
 obj: x7,8
Subject To
x1,2 + x1,3 + x1,4 + x1,5 + x1,6 + x1,7 + x1,8 = 1
x1,2 + x2,3 + x2,4 + x2,5 + x2,6 + x2,7 + x2,8 = 1
x1,3 + x2,3 + x3,4 + x3,5 + x3,6 + x3,7 + x3,8 = 1
x1,4 + x2,4 + x3,4 + x4,5 + x4,6 + x4,7 + x4,8 = 1
x1,5 + x2,5 + x3,5 + x4,5 + x5,6 + x5,7 + x5,8 = 1
x1,6 + x2,6 + x3,6 + x4,6 + x5,6 + x6,7 + x6,8 = 1
x1,7 + x2,7 + x3,7 + x4,7 + x5,7 + x6,7 + x7,8 = 1
x1,8 + x2,8 + x3,8 + x4,8 + x5,8 + x6,8 + x7,8 = 1
x1,2 + x2,3 + x3,4 + x4,5 + x5,6 + x6,7 + x7,8 >= 1
x1,3 + x2,4 + x3,5 + x4,6 + x5,7 + x6,8 >= 1
x1,4 + x2,5 + x3,6 + x4,7 + x5,8 >= 1
x1,5 + x2,6 + x3,7 + x4,8 >= 1
Binary
 x1,2 x1,3 x1,4 x1,5 x1,6 x1,7 x1,8 x2,3 x2,4 x2,5 x2,6 x2,7 x2,8 x3,4 x3,5 x3,6 x3,7 x3,8 x4,5 x4,6 x4,7 x4,8 x5,6 x5,7 x5,8 x6,7 x6,8 x7,8
End

You can submit the problem for free as an LP file at the NEOS server (check "Return .sol file" and add an email address).

I have tried all $1 \le n \le 18$. Here are some solutions:

$$n = 5: (1,5), (2,7), (3,4), (6,9), (8,10)$$ $$n = 8: (1,6), (2,8), (3,7), (4,11), (5,13), (9,10), (12,15), (14,16)$$ $$n = 9: (1,7), (2,9), (3,11), (4,8), (5,10), (6,15), (12,13), (14,17), (16,18)$$

It seems from the results that the problem has a solution if and only if:

$$n \equiv 0,1 \mod 4$$

But now we need a proof of that...

$\endgroup$
1
  • $\begingroup$ thank you for this great experimental evidence! The proof seems to be tricky though. I’m not even sure where to start exactly $\endgroup$ Commented Aug 18, 2023 at 11:09

You must log in to answer this question.