Results 1 to 3 of 3

Math Help - Pile of Coins

  1. #1
    Junior Member
    Joined
    Jun 2007
    Posts
    63

    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!
    Last edited by kkoutsothodoros; March 17th 2012 at 01:53 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

    Re: 100 Piles of Coins

    Quote Originally Posted by kkoutsothodoros View Post
    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.)
    Last edited by undefined; March 18th 2012 at 08:20 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2007
    Posts
    63

    Re: 100 Piles of Coins

    Thank you. I know how to do the other half.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: June 20th 2011, 04:55 PM
  2. Replies: 2
    Last Post: March 12th 2011, 11:15 AM
  3. please can anybody give the height of the pile
    Posted in the Geometry Forum
    Replies: 8
    Last Post: January 23rd 2011, 12:28 PM
  4. five men, a monkey, and a pile of coconuts
    Posted in the Algebra Forum
    Replies: 9
    Last Post: March 13th 2010, 09:59 AM
  5. Rate of increase on conical pile
    Posted in the Calculus Forum
    Replies: 1
    Last Post: December 1st 2009, 03:28 AM

Search Tags


/mathhelpforum @mathhelpforum