Câu hỏi 53
Cho $n \gt 1$ là một số nguyên dương. Claire viết $n$ số thực dương đôi một khác nhau $x_{1}, x_{2}, \ldots, x_{n}$ thành một hàng trên bảng. Trong mỗi bước, William có thể xóa một số $y$ và thay nó bằng $\frac{1}{y}$ hoặc $y+1$ tại cùng vị trí. Mục tiêu của anh ấy là thực hiện một dãy bước sao cho khi kết thúc, các số tăng ngặt từ trái sang phải.
a. Chứng minh rằng tồn tại một hằng số dương $A$, không phụ thuộc vào $n$, sao cho William luôn có thể đạt mục tiêu với nhiều nhất $A n \log n$ bước.
b. Chứng minh rằng tồn tại một hằng số dương $B$, không phụ thuộc vào $n$, sao cho Claire có thể chọn các số ban đầu để William không thể đạt mục tiêu với ít hơn $B n \log n$ bước.
a. Chứng minh rằng tồn tại một hằng số dương $A$, không phụ thuộc vào $n$, sao cho William luôn có thể đạt mục tiêu với nhiều nhất $A n \log n$ bước.
b. Chứng minh rằng tồn tại một hằng số dương $B$, không phụ thuộc vào $n$, sao cho Claire có thể chọn các số ban đầu để William không thể đạt mục tiêu với ít hơn $B n \log n$ bước.