Track / Stage 6 / 94 of 400 #1094 of 1964

Problem 1094

National olympiad, first round

Combinatorics Difficulty 6.1 Prove it

4. let $n$ be a natural number. There are $n+1$ bowls in a row, numbered from left to right with the numbers $0,1, \ldots, n$ . At the beginning there are $n$ stones in bowl 0 and no stones in the other bowls. Sisyphus wants to move these $n$ stones into bowl $n$ . To do this, Sisyphus moves exactly one stone from a bowl $i$ with $k$ stones to the right by at most $k$ bowls in each move, i.e. to a bowl with a number less than or equal to $k+i$ . Let $T$ be the minimum number of moves that Sisyphus needs to move all the stones into the bowl $n$ . Show that it holds:

$T \geq\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\ldots+\left\lceil\frac{n}{n}\right\rceil$

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution: (David) We assign each piece a unique number $k \in\{1,2, \ldots, n\}$ and call this number its priority. When Sisyphus makes a move, he chooses a square and moves from this square oBdA the stone with the highest possible priority (this is allowed because the stones are indistinguishable). With this additional rule, we arrive at the following observation:

The stone with priority $k$ can only be moved if there is no stone with a higher priority on its square. So if we move stone $k$ , there must be no more than $k$ stones on its square at that time. This means that stone $k$ can only be moved by a maximum of $k$ in each move. In order to move it from bowl 0 to bowl $n$ , a total of at least $\left\lceil\frac{n}{k}\right\rceil$ moves are necessary. Since Sisyphus can only move one stone in each move, we can add up the moves required for all stones and obtain the desired expression.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.