Question 12
Given a positive integer $n$ and a game board consisting of $n+1$ square fields arranged in a row, numbered from left to right from $0$ to $n$. At the start of the game there are $n$ stones on field no. $0$ and the other fields are empty.
A patient player now chooses, for each move, a field with $k \neq 0$ stones and moves one of them at most $k$ fields to the right. The stone must stay on the board. His goal is to bring all $n$ stones to field no. $n$ by a sequence of such moves.
Prove that the player cannot achieve this goal with fewer than $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$ moves. (Here $\lceil x\rceil$ denotes the smallest integer that is not less than $x$.)
A patient player now chooses, for each move, a field with $k \neq 0$ stones and moves one of them at most $k$ fields to the right. The stone must stay on the board. His goal is to bring all $n$ stones to field no. $n$ by a sequence of such moves.
Prove that the player cannot achieve this goal with fewer than $\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$ moves. (Here $\lceil x\rceil$ denotes the smallest integer that is not less than $x$.)