[Math] Number of ways of cutting a stick such that the longest portion is of length n

combinationscombinatoricsinteger-partitionspermutations

We are given a stick of length $L$ (say). We make cuts such that the longest piece is of length $n$ (say) at most.
What are the minimum number of pieces we will get and in how many ways this can be done? e.g

We have a stick of length 7. We want the longest piece of the stick to be of length 3 at most.

Soln. :The minimum number of pieces is 3 and there are 6 ways to make 2 cuts :

  1. positions: 1 4 (length of portions will be 1(0-1), 3(1-4), 3(4-7))

  2. positions: 3 4 (length of portions will be 3,1,3)

  3. positions: 3 6 (length of portions will be 3,3,1)

  4. positions: 2 4 (length of portions will be 2,2,3)

  5. positions: 2 5 (length of portions will be 2,3,2)

  6. positions: 3 5 (length of portions will be 3,2,3)

How can this be solved for large values of $L$ and $n$?

Best Answer

Try L=8, n=2; that means k=4 and applying the above formula, its 5, which i think is incorrect. I cant be making 4 cuts in such a way that i get only 4 pieces of size 2 or less.

the correct answer is one (as i can do this in only one way)

Related Question