Question 63
Let $n$ be a natural number. King Arthur has invited $2^n - 1$ knights to an audience in Camelot. Merlin the Magician arranged the knights in a list numbered from $1$ to $2^n - 1$. It turned out that any two knights with numbers $a, b, a \lt b$ are friends if and only if $0 \le b - 2a \le 1$. The king chose a natural number $k$ and ordered Merlin to make a new list with the following requirement. For each $1 \le i \le 2^n - k - 1$, all friends of the knight with sequence number $i$ (in the new list) must be in positions among $1, 2, \dots, i + k$. Prove that the smallest $k$, for which Merlin can fulfil Arthur's wish, satisfies the condition
$$
\frac{1}{100} \cdot \frac{2^n}{n} \le k \le 100 \cdot \frac{2^n}{n}.
$$
(Dragomir Grozev)
$$
\frac{1}{100} \cdot \frac{2^n}{n} \le k \le 100 \cdot \frac{2^n}{n}.
$$
(Dragomir Grozev)