Thread: 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.

Hello, pranay!

If one has a stick of length , 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 day
one can give 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?



- - . . . . . . . .






. . 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 into powers-of-2.


For example: .n = 100 requires 6 cuts.

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