Question 53
Let $n \gt 1$ be a positive integer. Claire writes $n$ distinct positive real numbers $x_{1}, x_{2}, \ldots, x_{n}$ in a row on a blackboard. In a move, William can erase a number $y$ and replace it with either $\frac{1}{y}$ or $y+1$ at the same location. His goal is to make a sequence of moves such that after he is done, the numbers are strictly increasing from left to right.
a. Prove that there exists a positive constant $A$, independent of $n$, such that William can always reach his goal in at most $A n \log n$ moves.
b. Prove that there exists a positive constant $B$, independent of $n$, such that Claire can choose the initial numbers such that William cannot attain his goal in less than $B n \log n$ moves.
a. Prove that there exists a positive constant $A$, independent of $n$, such that William can always reach his goal in at most $A n \log n$ moves.
b. Prove that there exists a positive constant $B$, independent of $n$, such that Claire can choose the initial numbers such that William cannot attain his goal in less than $B n \log n$ moves.