Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
  • 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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