IMO Shortlist 2018 problem C3

  Avg: 0,0
  Avg: 7,0
Dodao/la: arhiva
3. listopada 2019.

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 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 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 \rceilturns. (As usual, \lceil x \rceil stands for the least integer not smaller than x. )