Question 157
Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $(n+1)$ squares in a row, numbered from $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of those stones and moves it to the right by at most $k$ squares (the stone should stay within the board). Sisyphus's aim is to move all $n$ stones to square $n$.
Prove that Sisyphus cannot reach the aim in less than
$$
\left[ \frac{n}{1} \right] + \left[ \frac{n}{2} \right] + \left[ \frac{n}{3} \right] + \dots + \left[ \frac{n}{n} \right]
$$
turns. (As usual, $[x]$ stands for the least integer not smaller than $x$.)
Prove that Sisyphus cannot reach the aim in less than
$$
\left[ \frac{n}{1} \right] + \left[ \frac{n}{2} \right] + \left[ \frac{n}{3} \right] + \dots + \left[ \frac{n}{n} \right]
$$
turns. (As usual, $[x]$ stands for the least integer not smaller than $x$.)