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

Question

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$?

Answer 1

The minimum number of pieces would be $k=\lceil \frac{L}{n} \rceil$. Because you want to put as much as you can in each piece to minimise the number of pieces. Therefore, you want to have each piece to have the length $n$. There can be $\lfloor \frac{L}{n} \rfloor$ piece of length $n$, plus one piece of a length less than $n$.

Having the number of pieces $k$, you may use stars and bars method to deal with the rest. First you compute the number of possible positions, while having no upper limit for any of the pieces. So, the problem is as below

$$x_1+x_2+\ldots+x_k=L-k$$

and the solution is

$$\binom{L-1}{k-1}$$

Then, you need to take some possibilities, that have lengths greater than $n$, out. To do so, you take one of $x_i$ at a time and choose its length to be $n$. There are $\binom{k}{1}=1$ ways to choose one. Then, for each $x_i$, solve the following problem.

$$x_1+x_2+\ldots+x_k=L-(k+n)$$

$$\binom{L-n-1}{k-1}$$

The final solution would be

$$\binom{L-1}{k-1}-k\binom{L-n-1}{k-1}$$

Answer 2

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)

Answer 3

The basic Idea is : Given example L=17, n=4. One such way to distribute this is :

4|4|4|4|1

Now, we can move some values from the first 4 slots to the last slot '1'. We can add a max value of 3 to the last slot since [1+3=n] and we cannot have a piece with >n length.

So, by using multinomial theorem, we need to find solutions to: x1+x2+x3+x4 <= 3 which is the same as x1+x2+x3+x4+x5=3.

We know that the formula for non-negative solutions of x1+x2+x3....+xm=p is: (p+m-1)C(m-1) Reference : https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Its easy to see that m = (ceil(L/n)) and p = (n - L%n).

Special case : When L%n=0, then there is only 1 way to cut and number of pieces = L/n.

Edit :

Related Problem for Reference : https://www.codechef.com/MAY17/problems/SANDWICH