, 2023

Solution:

We use divide and conquer. The base case $n=1$ is clear. Let $f(n)$ denote the number of moves required for $n$ numbers. Let $x=\lceil n / 2\rceil$ and $y=\lfloor n / 2\rfloor$. Then, William can reach his goal by the following process:
- Use $f(x)$ moves to make the first $x$ numbers a strictly decreasing sequence.
- Use $f(y)$ moves to make the last $y$ numbers a strictly decreasing sequence.
- Add one to all the numbers, taking $n$ moves. At this point, all the numbers are greater than $1$.
- Take the reciprocal of all the numbers, using $n$ moves. At this point, all the numbers are in $(0,1)$. Moreover, the first $x$ numbers and the last $y$ numbers form a strictly increasing sequence.
- Finally, add one to the last $y$ numbers.
Hence, we have
$$f(n) \leq f\left(\left\lceil\frac{n}{2}\right\rceil\right)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+2 n+\frac{n}{2}$$
giving $f(n)=O(n \log n)$.

Double Counting Solution to (b)

Take $B=0.01$, and assume $n$ is sufficiently large. Assume for contradiction that William has an algorithm for all possible initial numbers. We first note that if William uses less than $x$ moves, then he can keep adding one to the last number until he uses exactly $x$ moves. We henceforth assume that William has an algorithm that uses $x \leq 0.01 n \log n$ moves.
Take arbitrary initial numbers. We claim that if William always has an algorithm that results in the final numbers being increasing after $x$ moves, then he in fact has an algorithm which can result in the final numbers being in any given ordering after $x$ moves. This is because he can permute the indices of the initial numbers, operate on the permuted numbers to be increasing, and then take the permutation back such that the final numbers are now in the specified ordering after applying $x$ moves (note that each move only acts and depends on one of the values.) In particular, this implies that by applying $x$ moves, William can produce $\geq n!$ possible final states. We now claim this is impossible.
Indeed, there are $\binom{x+n-1}{n-1}$ ways to distribute $x$ moves to each of the $n$ numbers. Moreover, there are two options for each move, giving $2^{x}$ choices across all the $x$ moves. Thus, William has
$$2^{x}\binom{x+n-1}{n-1}$$
choices of moves. When $n$ is sufficiently large, we have
$$\begin{aligned} 2^{x}\binom{x+n-1}{n-1} & \leq 2^{0.01 n \log n} \frac{(x+n-1)^{n-1}}{(n-1)!} \\ & \leq e^{0.01 n \log n} \frac{(0.1 n \log n)^{n}}{\left(\frac{n}{10}\right)^{n}} \\ & = n^{0.01 n}(\log n)^{n} \\ & = n^{0.01 n} n^{\log \log n}<\left(\frac{n}{10}\right)^{n}<n! \end{aligned}$$
which is a contradiction.

Constructive Solution to (b)

By shifting $B$ it suffices to prove this for sufficiently large $n$ (for the smaller ones just make sure $B n \log n<1$.) We now prove the result when $n=k^{2}$ is a perfect square; the general case follows by shifting $B$ appropriately. Choose the $x_{i}$ such that
$$\begin{gathered} x_{k^{2}-k+1}>x_{k^{2}-2 k+1}>\ldots>x_{1} \\ >x_{k^{2}-k+2}>x_{k^{2}-2 k+2}>\ldots>x_{2} \\ \ldots \\ >x_{k^{2}}>x_{k^{2}-k}>\ldots>x_{k} . \end{gathered}$$
One may check that there exists no strictly increasing or decreasing subsequence of the $\{x_{i}\}$ of length $>k$. Now, if William uses less than $B k^{2} \log \left(k^{2}\right)$ moves, then evidently there exists at least $k^{2} / 2$ elements on which he applies at most $2 B \log \left(k^{2}\right)$ moves. Let $\left\lceil 2 B \log \left(k^{2}\right)\right\rceil=N$; note that the number of possible sequences of moves that can be applied to each of these $\leq k^{2} / 2$ elements is $\leq 2^{N}+2^{N-1}+\ldots+1<2^{N+1}$. Note that $N=\Theta\left(\log k^{2}\right)$ and so $2^{N+1}=k^{\Theta(1)}$; hence by choosing a sufficiently small $B$ we can ensure that $2^{N+1}<k / 2$. This now implies that there exists a set $S$ of $>k$ elements on which the same sequence of moves are applied. Note by our choice of $\{x_{i}\}$ we know that within $S$, there exists both a pair $(x_{i}, x_{j})$ for which $i<j$ and $x_{i}<x_{j}$, and a pair where $i<j$ yet $x_{i}>x_{j}$. But note that any composition of moves acts as a rational function which is monotonic on $(0, \infty)$ (as it has no roots or poles within the given domain.) Hence this implies that either the increasing or decreasing pair must become decreasing after being operated upon by the same sequence of moves, and hence William has not achieved his goal, a contradiction. This thus proves the problem for an appropriate choice of $B$.