MathDB
Long game to go..

Source: IMO SL 2018 C3

July 17, 2019
combinatoricsIMO Shortlistgameilostthegame

Problem Statement

Let nn be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of n+1n + 1 squares in a row, numbered 00 to nn from left to right. Initially, nn stones are put into square 00, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with kk stones, takes one of these stones and moves it to the right by at most kk squares (the stone should say within the board). Sisyphus' aim is to move all nn stones to square nn. Prove that Sisyphus cannot reach the aim in less than ⌈n1⌉+⌈n2⌉+⌈n3⌉+⋯+⌈nn⌉ \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, ⌈x⌉\lceil x \rceil stands for the least integer not smaller than xx. )
Back to ProblemsView on AoPS