500+ followers problem

Probability Level 4

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.

1 solution

Khang Nguyen Thanh
Aug 7, 2017

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.

(Love this question btw)

Remember, to show that something is a minimum, we have to
1. Show that no smaller number works.
2. Show that it can be achieved.

You have done 2, but not 1. How do we know that we cannot do so in 8 minutes?

Calvin Lin Staff - 3 years, 10 months ago

After each step, the number of remaining classes is greater than or equal to a half of the number of beginning classes.

So to reduce from 500 classes to 1 classes, we need at least 9 steps.

Khang Nguyen Thanh - 3 years, 10 months ago

"the number of remaining classes is greater than a half of the number of beginning classes"

How do you know this? Note that if the statement is true, then we will never end. When we get down to 1 clases (beginning), then the number of remaining classes is greater than 1/2, so it is 1.

(You have essentially the right idea, and just need to figure out how to express it in a clear way.)

Calvin Lin Staff - 3 years, 10 months ago

@Calvin Lin – Beginning, we have 500 classes because piles have distinct number of stones. In the last, we have 1 class of 500 empty piles.

Since $2n\ge m$ , the number of remaining classes after each step is greater than or equal to a half of the number of beginning classes.

For example, after first step, the number of remaining classes is at least 250. After second step, the number of remaining classes is at least 125, and so on.

Therefore, we need at least 9 steps to get 1 class.

Khang Nguyen Thanh - 3 years, 10 months ago

@Khang Nguyen Thanh – Yes, you have the right ideas involved, but the solution write-up is somewhat sloppy. This is why I'm being pedantic about the rigor.

"the number of remaining classes after each step is greater than or equal to a half of the number of beginning classes."
As mentioned, if we have $m=1$ class left, then this claim would mean that $n = 1$ and so we would always be stuck with that 1 class. is the claim conditional on $m > 1$ ?
If we need 9 steps to get to 1 class, doesn't that mean that we need one more step to clear that class?

Calvin Lin Staff - 3 years, 10 months ago

500+ followers problem

The answer is 9.

1 solution

0 pending reports