olymmath

ISL 2018 C3

    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 0 to nn from left to right. Initially, nn stones are put into square 0, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with kk stones, takes one of those stones and moves it to the right by at most kk squares (the stone should stay 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+\cdots+\left\lceil\frac{n}{n}\right\rceil turns. (As usual, ⌈x⌉\lceil x\rceil stands for the least integer not smaller than xx.) (Netherlands)

    Official text Transcription from NuminaMath olympiads, checked word for word against the official paper. Quoted with source.

    Official text: IMO 2018 Shortlist booklet, page 6.

    Solutions

    Official solution Solution 1 by the IMO Problem Selection Committee

    The terms of the source let olymmath link to this solution but not copy it. Read the solution (IMO official site).

    Locator isl/2018/c3 · Tag W0YHNTDGJ5 · Edit this page on GitHub · Keys: j next, k previous