IMO 2018 Shortlist C3
Let n be a given positive integer. Sisyphus performs a sequen e of turns on a board onsisting of n 1 squares in a row, n...
Category: Combinatorics
Problem
Let n be a given positive integer. Sisyphus performs a sequen e of turns on a board
onsisting 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 hooses any nonempty square, say with k stones, takes one of those stones and moves it to the right by at most k squares (the stone should stay within the board). Sisyphus' aim is to move all n stones to square n. Prove that Sisyphus annot rea h the aim in less than Qn U
Qn
U
Qn U ¨¨¨ `
Qn
n
U
turns. (As usual, rxs stands for the least integer not smaller than x.)
(Netherlands)