Câu hỏi 63
Cho $n$ là một số tự nhiên. Vua Arthur mời $2^n - 1$ hiệp sĩ đến yết kiến tại Camelot. Pháp sư Merlin xếp các hiệp sĩ thành một danh sách đánh số từ $1$ đến $2^n - 1$. Hóa ra hai hiệp sĩ bất kì có số thứ tự $a, b, a \lt b$ là bạn của nhau khi và chỉ khi $0 \le b - 2a \le 1$. Nhà vua chọn một số tự nhiên $k$ và ra lệnh cho Merlin lập một danh sách mới với yêu cầu sau. Với mỗi $1 \le i \le 2^n - k - 1$, tất cả bạn của hiệp sĩ ở vị trí thứ $i$ (trong danh sách mới) phải ở các vị trí trong số $1, 2, \dots, i + k$. Chứng minh rằng số $k$ nhỏ nhất mà Merlin có thể thực hiện mong muốn của vua Arthur thỏa mãn điều kiện
$$
\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)