5
$\begingroup$

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$

$\endgroup$
4
$\begingroup$

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


Edit: (Revisited this answer after a few years in order to add proof)

Allowed solutions consist of an algorithm that describes a sequence of cuts and (at no cost) concatenation operations. I tis clear that any such solution can be brought into this standard form:

  1. Cut some of the unit length input ropes into pieces.
  2. Combine the pieces into the $N$ output ropes (plus possibly some waste)

It doesn't harm to allow the following more general form:

  1. Combine unit length input ropes into some integer length intermediate ropes.
  2. Cut the intermediate ropes into pieces
  3. Combine the pieces into the $N$ output ropes and combine the waste pieces (if there are any) into a "waste rope"

Our task is to find an algorithm that minimizes the cuts performed in step 2. To do so we consider all algorithms that achieve the minimal number of cuts, and among these consider the one that minimizes the number of intermediate ropes produced in step 1.

If two of the pieces an intermediate rope is cut into end up in the same output rope, we can rearrange the locations of the pieces on the uncut rope in such a manner that they are adjacent, which allows us to save a cut. By the minimality of our algorithm, this does not happen. That is: Each intermediate rope contains at most one contiguous piece from each output rope; note that this applies also to the waste rope.

Assume two distinct intermediate ropes each contain a piece of the same output rope, say one intermediate rope is cut into pieces of lengths $a_0, a_1,\ldots, a_r$ by $r$ cuts and the other is cut into pieces of lengths $b_0,b_1,\ldots,b_s$ by $s$ cuts and that the pieces of length $a_0,b_0$ both end up in the same output rope. Then we can instead combine these two intermediate ropes into one and cut it into $a_0+b_10, a_1,\ldots, a_r, b_1,\ldots,b_s$ with the same number $r+s$ of cuts, but with less intermediate ropes. By our choice of algorithm, this is impossible. Therefore: Each output rope is contained in exactly one intermediate rope; again, this also applies to the waste rope. In particular, there is at most one intermediate rope containing waste. We may additionally assume (by rearranging parts) that the waste part occurs at the end in its intermediate rope.

A wasteless intermediate rope as a positive length $\in \Bbb Z\cap C\Bbb Z$. If $C$ is irrational, this is not possible. Hence in this case there is only one intermediate rope and it requires $$N $$ cuts at positions $C, 2C, \ldots, NC$.

If $C=\frac pq$ with $\gcd(p,q)=1$ is rational, the length $\ell$ of a wasteless intermediate rope must be $\in \Bbb Z\cap C\Bbb Z=p\Bbb Z$ and it is cut at positions $C, 2C, 3C,\ldots$. If $\ell>p$, we could save a cut by replacing it with intermediate ropes of lengths $p$ and $\ell-p$. By minimality, this is not possible, hence each wasteless rope has length $p$ and needs $q-1$ cuts to produce $q$ output ropes of length $\frac pq$. By the same argument, the number of output ropes in the wasteful intermediate rope must be $<q$ and requires just as many cuts. We thus have described an algorithm that for $N=qM+R$, $ 0\le R<q$, requires $$(q-1)M+R =N-\left\lfloor\frac Nq\right\rfloor $$ cuts and is optimal.

$\endgroup$
1
$\begingroup$
  • 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.