# Cut the rope puzzle

This question was asked to me in an interview, I still cannot think of its solution. Can anyone help? Following is the question:

Given an infinite number of ropes of length $R$, you have to calculate the minimum number of cuts required to make $N$ ropes of length $C$. You can append ropes one after the other to make ropes of length $2R, 3R, 4R, \ldots$

-

Wlog. $R=1$. If $C$ is an integer, no cuts are required. Otherwise let $c=C-\lfloor C\rfloor$, a real number between $0$ and $1$. Each rope must finally contain at least one cut end, thus the number of cuts is at least $\frac N2$ and it is easily solvable with $N$ cuts.

Indeed, $\lceil \frac N2 \rceil$ is enough if $c=\frac12$.

If $c=\frac23$, one can produce $\lceil \frac23 N\rceil$ pieces of $\frac23$ and combine the $\frac13$ rests for the remaining ropes, hence $\lceil \frac23 N\rceil$ cuts suffice.

If $c=\frac13$, then $\lceil \frac23 N\rceil$ cuts suffice again.

For $c=\frac34$ or $c=\frac14$, I can do it with $\lceil \frac34 N\rceil$ cuts, for $\frac k 5$ with $1\le k\le 4$, I can do it with $\lceil \frac45N\rceil$ cuts.

A pattern sems to emerge here, but I'm not sure if it is really optimal: $c=\frac pq$ requires $\lceil (1-\frac1q)N\rceil$ cuts. And if $c$is irrational, $N$ cuts are needed, I suppose.

Remark: If the final result is correct, there is no need to go for $c$, one can directly say that $\lceil (1-\frac1q)N\rceil$ cuts are needed if $\frac CR=\frac pq$.

-
• Suppose there are $k,m\in \mathbb{N}$ such that $k\cdot R=m \cdot C$ and the minimum $m$ is $m_0$.

1. For $N=r\cdot m_0, \ \ r \in \mathbb{N}$ the minimum number of cuts is $r\cdot (m_0-1)$ (Make $r$ ropes of length $m_0\cdot C$ and with $m_0-1$ cuts in each rope you can produce $m_0$ ropes of length $C$).
2. If $N\neq r\cdot m_0, \ \forall r \in\mathbb{N}$ then you can write $N=r\cdot m_0 +N_0, \text{ for some } \ r,N_0 \in\mathbb{N} \cup \{0\}$ with $0<N_0<m_0$. Use 1. to make $r\cdot m_0$ ropes of length $C$ and 3. to make $N_0$ ropes of length $C$.
3. If $N<m_0$ make a rope of length $>N\cdot C$ and use $N$ cuts to make $N$ ropes of length $C$.
• If $k\cdot R\neq m \cdot C$ for any $k,m\in \mathbb{N}$ then make a rope of length $>N\cdot C$ and use $N$ cuts to make $N$ ropes of length $C$.

-