MathDB

Let

n>1

be a positive integer. Claire writes

n

distinct positive real numbers

x_1, x_2, \dots, x_n

in a row on a blackboard. In a

<span class='latex-italic'>move</span>,

William can erase a number

x

and replace it with either

\tfrac{1}{x}

x+1

at the same location. His goal is to perform a sequence of moves such that after he is done, the number are strictly increasing from left to right.
[*]Prove that there exists a positive constant

A,

independent of

n,

such that William can always reach his goal in at most

An \log n

moves. [*]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

Bn \log n

moves.

Problem Statement