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_1{v}_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:=\lceil 16\cdot \frac{2^n}{n}\rceil$$

This proves the upper bound. □