There are 500 piles of stones with 1 stone in the first pile, 2 stones in the second pile, 3 stones in the third pile, ..., 500 stones in the 500th pile.

In each minute, you can choose a positive integer $k$ and remove exactly $k$ stones from every pile which has at least $k$ remaining stones in it.

What is the minimum number of minutes you need in order to remove all stones from all piles?

The answer is 9.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

We group all piles have the same number of stones into a class. Initially, we have 500 classes, each class has 1 pile of stones. The last configuration is 1 class of 500 empty piles.

Suppose that there are $m$ classes (including class of groups with 0 stones) before removing stones, and there are $n$ classes after removing stones from $i$ classes.

If before removing stones 2 piles belong to 2 different classes, 2 piles still belong to 2 different classes after removing stones. So, the number of remaining classes is greater than or equal to $i$ , or $n\ge i$ .

While removing stones, there are $m-i$ classes is not effected, so $n\ge m-i$ .

From 2 above inequalities, we get $2n\ge m$ .

Since $2^8<500<2^9$ , we need at least 9 minutes to remove all stones from all piles.

This is a valid way to remove all stones from all piles. In each step, we can choose $k$ is $2^8,2^7,\ldots, 2^0$ respectively.