Competition problem — Combinatorics

Library / /98 of 397

Combinatorics Difficulty 5.3 AIME, harder Prove it Taiwan

Old Zhao, being a soldier, got bored, so he drew $n + 1$ cells on the ground arranged in a row ( $n$ being a positive integer), numbered from left to right as cell 0 through cell $n$ . At the start, cell 0 has $n$ stones, while all other cells are empty. In each turn, Old Zhao first selects a nonempty cell, and suppose it contains $k$ stones. He then takes one stone from the selected cell and moves it to the right by at most $k$ cells (the stone must not go past the rightmost cell). Old Zhao's goal is to get all the stones into cell $n$ .

Prove that the number of turns required for Old Zhao to achieve his goal is at least
$\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,$
where $\lceil x \rceil$ denotes the smallest integer not less than $x$ .

Solution

Let us number the stones 1 through $n$ , and without loss of generality, assume that whenever Old Zhao moves a stone, he always moves the stone with the largest number in that cell. Now, notice that when Old Zhao moves stone number $k$ , that cell contains at most $k$ stones, so stone number $k$ can move at most $k$ steps at a time. In other words, for stone number $k$ to move to cell $n$ , it requires at least $\left\lceil \frac{n}{k} \right\rceil$ steps, and thus the original statement is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.