Q10 Matemática  (IMO Shortlist 2018)

Seja $n$ um dado inteiro positivo. Sísifo executa uma sequência de voltas em um tabuleiro composto por $n+1$ quadrados em fila, numerados de $0$ a $n$ da esquerda para a direita. Inicialmente, $n$ pedras são colocadas no quadrado $0$, e os outros quadrados estão vazios. A cada turno, Sísifo escolhe qualquer casa não vazia, digamos com pedras $k$, pega uma dessas pedras e a move para a direita em no máximo $k$ casas (a pedra deve estar dentro do tabuleiro). O objetivo de Sísifo é mover todas as pedras $n$ para o quadrado $n$. Prove que Sísifo não pode atingir o objetivo em menos de $$\lceil \frac{n}{1}\rceil +\lceil \frac{n}{2}\rceil +\lceil \frac{n}{3}\rceil +\cdots +\lceil \frac{n}{n}\rceil$$turns. (Como de costume, $\lceil x\rceil$ representa o menor inteiro não menor que $x$.)