TST for BMO

Let us construct a graph $T$ with vertex-set which is the set of all knights, numbered as in the first list. Two vertices are adjacent if the corresponding knights are friends. It can be seen that $T$ is a fully balanced binary tree - see fig. 1. We label each vertex with the knight's number in the first list. Let us assume the vertices can be arranged in a row $i_1, i_2, \dots, i_m$ as King Arthur requested, where $m = 2^n - 1$ and $i_j$ refers to the label of the corresponding vertex. There is a unique path in $T$, $i_1 = v_1v_2\dots v_\ell = i_m$ that connects the vertex labeled as $i_1$ and $i_m$. Clearly, $\ell \le 2(n-1) + 1$, because the longest path in $T$ has length $2(n-1)$. Note that the distance between the positions of $v_i$ and $v_{i+1}$ in the new list, is at most $k$. This means that $(\ell - 1)k \ge m - 1$ which yields
$$k \ge \frac{2^n - 2}{2n - 2} > \frac{2^n}{4n},$$
which proves the lower bound for $k$.

Now we will arrange the vertices of $T$ in a list. Let $\ell$ be a natural number which will be determined later. Denote by $v_1, v_2, \dots, v_s, s := 2^\ell$ the vertices of $T$ on the $\ell$-th level, and let $T(v_1), T(v_2), \dots, T(v_s)$ be the subtrees with roots in these points - see fig. 1. Each of them has exactly $2^{n-1-\ell}$ leaves.

We successively put in a list the vertices of $T$ as follows. First, we place the last level of vertices of $T(v_1)$, that is, its leaves. Then we put down the second to last level of $T(v_1)$ and the last level of $T(v_2)$. At the $i$-th step we place the $i$-th level of $T(v_1)$, counting from the bottom up (fig. 1), then the $i-1$-th level of $T(v_2)$ (from the bottom up) and so on, and finally - the last layer of $T(v_i)$ (i.e. its leaves). The number of vertices we place at the $i$-th step $i = 1, 2, \dots, s-\ell-1$ is equal to
$$\sum_{j=0}^{i-1} 2^{n-1-\ell-j} \le 2^{n-\ell}.$$
We follow these steps until one of the two events happens. 1) We reach the root $v_1$ of $T(v_1)$. 2) We place in the list the leaves of $T(v_s)$. The first event will

happen after $n-\ell$ steps and the second one - after $s = 2^\ell$ steps. To ensure that the second event occurs first we choose $\ell$ to be the largest positive integer for which $s = 2^\ell \le n - \ell$.

In this situation, at the s-th step we have put the leaves of $T(v_s)$ in the list. On the s + 1-th step we put in the list the remaining vertices of T. The number of all vertices in $T(v_s)$ without its last level does not exceed $2^{n-\ell-1}$. The number of vertices in $T(v_{s-1})$ without its last two layers does not exceed $2^{n-\ell-2}$ and so on. Adding the vertices of T up to its l-th level, we obtain that the number of the vertices ordered at the last step is at most
$$2 \cdot 2^{\ell} + 2^{n-\ell} \le 2 \cdot 2^{n-\ell} \le 8 \cdot \frac{2^n}{n}$$
since $2^{n+2} \ge n$. Clearly, for any vertex $v$, placed at position $j$ in the first $s$ steps, all of its neighbours in $T$, that are placed after it, are in positions with numbers not exceeding $j+2 \cdot 2^{n-\ell} \le j+8 \cdot \frac{2^n}{n}$. Taking into account the number of vertices added in the last step, we get that in the constructed list the condition imposed by the king holds for
$$k := \left\lceil 16 \cdot \frac{2^n}{n} \right\rceil$$

This proves the upper bound. □