MathDB

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

0

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 these stones and moves it to the right by at most

k

squares (the stone should say within the board). Sisyphus' aim is to move all

n

stones to square

n

. Prove that Sisyphus cannot reach the aim in less than

\left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil

turns. (As usual,

\lceil x \rceil

stands for the least integer not smaller than

x

. )

C3