1. ## 100 Piles of Coins

Hi all,

I came across this problem:

We have 100 piles of coins, with the ith pile containing exactly i coins. We wish to remove
all the coins in a series of steps. In each step we are allowed to take away coins from as many
piles as we wish, but we have to take the same number of coins from each such pile. Show
that we can remove all the coins in 7 steps, but that it is impossible to do so in 6.

My solution is as follows:

Focus on piles 1, 2, 4, 8, 16, 32, and 64. We need at least 1 step to remove the 1 coin in pile 1. We'll need at least 1 more step to remove the coins in pile 2 since we could only have removed 1 from the step mentioned previously. We'll need at least 1 more step to remove all coins from pile 4 because we could have removed at most 1 + 2 = 3 from 2 steps mentioned before. This argument can be continued to show we need at least 7 steps since 64 = 2^7.

Could someone just look it over and verify.

Thanks!

2. ## Re: 100 Piles of Coins

Originally Posted by kkoutsothodoros
Hi all,

I came across this problem:

We have 100 piles of coins, with the ith pile containing exactly i coins. We wish to remove
all the coins in a series of steps. In each step we are allowed to take away coins from as many
piles as we wish, but we have to take the same number of coins from each such pile. Show
that we can remove all the coins in 7 steps, but that it is impossible to do so in 6.

My solution is as follows:

Focus on piles 1, 2, 4, 8, 16, 32, and 64. We need at least 1 step to remove the 1 coin in pile 1. We'll need at least 1 more step to remove the coins in pile 2 since we could only have removed 1 from the step mentioned previously. We'll need at least 1 more step to remove all coins from pile 4 because we could have removed at most 1 + 2 = 3 from 2 steps mentioned before. This argument can be continued to show we need at least 7 steps since 64 = 2^7.

Could someone just look it over and verify.

Thanks!
You have only proven half of what the question asked, that the coins can't be removed in 6 or less steps. Hint: Think about binary representations.

Edit: You should correct your final line as 64 = 2^6. (You are proving for n=7 that it takes at least n steps if there are at least 2^(n-1) piles, and note that "this argument can be continued to show.." is shorthand for mathematical induction, if you want to prove it for all natural numbers n.)

3. ## Re: 100 Piles of Coins

Thank you. I know how to do the other half.