A permutation problem

Question

Here I ask a question on permutations of $n$ distinct real numbers.

QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\ldots,a_n$ with $b_1 = a_1$ such that the $n−1$ numbers $$|b_1 −b_2|,\ |b_2 −b_3|,\ \ldots,\ |b_{n−1} −b_n|$$ are pairwise distinct ?

Actually, I formulated this question in 2013 and conjectured that the answer should be positive. If $a_1$ is the smallest (or largest) number among $a_1,\ldots,a_n$, then it is easy to construct a desired permutation $(b_1,\ldots,b_n)$. In fact, when $a_1<a_2<\ldots<a_n$ we may take $$(b_1,b_2,\ldots,b_n)=(a_1,a_n,a_2,a_{n-1},\ldots,a_{\lfloor n/2\rfloor+1})$$ to meet the purpose.

In 2015, Francesco Monopoli [Electron. J. Combin. 22(2015), no. 3, #P3.20] showed that my question for $a_1,\ldots,a_n$ has a positive answer if the set $A=\{a_1,a_2,\ldots,a_n\}$ forms an arithmetic progression.

As any path is a tree, in 2014 I made the following conjecture which unifies my question and Ringel and Kotzig's graceful tree conjecture.

Conjecture. Let $a_1,a_2,\ldots,a_n$ be $n > 1$ distinct real numbers, and let $T$ be any tree with vertices $v_1,\ldots,v_n$, where $v_1$ is a leaf (i.e., $\deg_T(v_1) = 1$). Then there is a bijection $f$ from the vertex set $V(T)$ of the tree $T$ to $A = \{a_1,\ldots,a_n\}$ with $f (v_1) = a_1$ such that those $|f (v_i)−f (v_j)|$ with $v_i$ and $v_j$ adjacent are pairwise distinct.

Any ideas towards the final solution of my question? Comments on the above general conjecture are also welcome!

Answer 1

A simple brute-force of trees yields a counter-example with $n = 7$. Let $\{a_1, \ldots, a_7\} = [7]$, $T$ be a path of four vertices $v_1, v_2, v_3, v_4$, with $v_4$ adjacent to $v_5, v_6, v_7$. If we fix $f(v_1) = 4$, the conjecture is failed. I have not come up with a simple proof yet (other than trying all options of $f$), may update later.

UPD: ok, here is the proof. Consider all options of $f(v_2)$:

• $f(v_2) = 3$ ($5$ is symmetrical). Note that in the set $\{1, 2, 5, 6, 7\}$ each element has another one with absolute difference $1$, hence for all options of $f(v_4)$ there is an index $j \in \{3, 5, 6, 7\}$ such that $|f(v_4) - f(v_j)| = |f(v_1) - f(v_2)| = 1$.

• $f(v_2) = 2$ ($6$ is symmetrical). The only element of $\{1, 3, 5, 6, 7\}$ not at distance $2$ from another element is $6$. But if $f(v_4) = 6$, there are distinct $i, j \in \{3, 5, 6, 7\}$ with $f(v_i) = 5$ and $f(v_j) = 7$, hence $|f(v_4) - f(v_i)| = |f(v_4) - f(v_j)| = 1$.

• $f(v_2) = 1$ ($7$ is symmetrical). The only element of $\{2, 3, 5, 6, 7\}$ not at distance $3$ from another element is $7$. Let $f(v_4) = 7$ and $f(v_3) = x$, but then $f(v_i) = 8 - x$ for a certain $i \in \{5, 6, 7\}$, and $|f(v_2) - f(v_3)| = |f(v_4) - f(v_i)| = x - 1$.