Results 1 to 2 of 2

Math Help - Cutting stick

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    Cutting stick

    If one has a stick of length n then what is the minimum number of cuts one can make on it to have n parts of it so that at the end of ith day one can give ith lenght of stick to someone ?
    E.g if the length of stick is 5 one can make 2 cuts as follows:
    First cut : length of 1 unit.
    Second cut: length of 1 unit.
    the remaining length is of 3 units which can be given on 3rd day , taking back the earlier 2 parts.
    E.g :
    if lenght is of lenght 6 then one can make 3 cuts:
    First cut: length of 1 unit.(give that on 1st day)
    Second cut : length of 2 units.(give this on 2nd day ,take back 1st part)
    Third day: give the remaing part(length of 3 units and take back parts of lenght 1 and 2)
    Fourth day: give part of lenght 1 (so total length given 3+1)
    Fifth day: cut the part of length 2 into 2 parts and give one part ,so total lenght given is 3+1+1
    Sixth day : give the remaining part of length 1 (so total given length 3+1+1+1=6).
    I have tried like:
    if the lenght is odd then answer is n - ceil(n/2.0) and if lenght is even then ans = n/2
    However i'm not too sure about it .
    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, pranay!

    If one has a stick of length \,n, then what is the minimum number of cuts
    one can make on it to have n parts of it so that at the end of k^{th} day
    one can give \,k units of stick to someone?

    This is a classic problem.

    A traveller has a chain of seven gold links
    . . and wants to stay seven days at an inn.
    The inn charges one link per night.
    The traveller agrees to pay one link per day.

    The innkeeper does not want seven cut links.
    . . He will accept the minimum number of cuts.

    How should the traveller cuts the links?



    - - . . . . . . . . \Uparrow






    . . Day. . Payment . . . . Action

    . . . 1 . . . . . 1 . . . . . . . Give 1
    . . . 2 . . . . . 2 . . . . Give 2, take 1
    . . . 3 . . . . 2+1 . . . . . Give 1
    . . . 4 . . . . . 4 . . . Give 4, take 1 & 2
    . . . 5 . . . . 4+1 . . . . . . Give 1
    . . . 6 . . . . 4+2 . . . . Give 2, take 1
    . . . 7 . . . 4+2+1 . . . . . Give 1



    In general, partition \,n into powers-of-2.


    For example: .n = 100 requires 6 cuts.

    . . 100 .= .1 + 2 + 4 + 8 + 16 + 32 + 37

    Last edited by Soroban; May 3rd 2011 at 10:43 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cutting a quadrilateral
    Posted in the Geometry Forum
    Replies: 2
    Last Post: November 24th 2010, 07:20 AM
  2. cutting the cube
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: October 15th 2010, 10:41 PM
  3. Breaking a stick.
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 26th 2009, 02:40 AM
  4. length of each stick
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 1st 2008, 08:02 AM
  5. [SOLVED] cutting cuboids!!
    Posted in the Geometry Forum
    Replies: 2
    Last Post: May 26th 2007, 11:04 PM

Search Tags


/mathhelpforum @mathhelpforum