Cortar el rompecabezas de la cuerda.

Question

Esta pregunta me la hicieron en una entrevista, todavía no puedo pensar en su solución. ¿Alguien puede ayudar? La siguiente es la pregunta:

Dado un número infinito de cuerdas de longitud$R$, debe calcular la cantidad mínima de cortes necesarios para hacer$N$ cuerdas de longitud$C$. Puede agregar cuerdas una tras otra para hacer cuerdas de longitud$2R, 3R, 4R, \ldots$

Answer 1

Wlog. $R=1$. Si $C$ es un número entero, sin cortes. De lo contrario vamos a $c=C-\lfloor C\rfloor$, un número real entre el$0$$1$. Cada cuerda finalmente debe contener al menos un extremo del corte, por lo tanto el número de cortes es, al menos, $\frac N2$ y es fácilmente solucionable con $N$ cortes.

De hecho, $\lceil \frac N2 \rceil$ es suficiente si $c=\frac12$.

Si $c=\frac23$, se puede producir $\lceil \frac23 N\rceil$ piezas de $\frac23$ y combinar las $\frac13$ descansa para el resto de las cuerdas, por lo tanto $\lceil \frac23 N\rceil$ cortes suficiente.

Si $c=\frac13$, $\lceil \frac23 N\rceil$ cortes suficiente de nuevo.

Para $c=\frac34$ o $c=\frac14$, lo puedo hacer con $\lceil \frac34 N\rceil$ cortes, para$\frac k 5$$1\le k\le 4$, lo puedo hacer con $\lceil \frac45N\rceil$ cortes.

Un patrón sems a surgir aquí, pero no estoy seguro de si es realmente óptimo: $c=\frac pq$ requiere $\lceil (1-\frac1q)N\rceil$ cortes. Y si $c$es irracional, $N$ recortes son necesarios, supongo.

Nota: Si el resultado final es correcto, no hay necesidad de ir a por $c$, uno directamente se puede decir que el $\lceil (1-\frac1q)N\rceil$ recortes son necesarios si $\frac CR=\frac pq$.

Answer 2

• Supongamos que hay $k,m\in \mathbb{N}$ tal que $k\cdot R=m \cdot C$ y el mínimo de $m$$m_0$.

  1. Para $N=r\cdot m_0, \ \ r \ \ en \mathbb{N}$ the minimum number of cuts is $r\cdot (m_0-1)$ (Make $r$ cuerdas de longitud $m_0\cdot C$ e con $m_0-1$ cortes en cada cuerda puede producir $m_0$ cuerdas de longitud $C$).
  2. Si $N\neq r\cdot m_0, \ \forall r \in\mathbb{N}$, entonces usted puede escribir $N=r\cdot m_0 +N_0, \text{ for some } \ r,N_0 \in\mathbb{N} \cup \{0\}$$0<N_0<m_0$. Uso 1. para hacer $r\cdot m_0$ cuerdas de longitud $C$ y 3. para hacer $N_0$ cuerdas de longitud $C$.
  3. Si $N<m_0$ hacer una cuerda de longitud $>N\cdot C$ y el uso de $N$ recortes para hacer $N$ cuerdas de longitud $C$.

• Si $k\cdot R\neq m \cdot C$ cualquier $k,m\in \mathbb{N}$, a continuación, hacer una cuerda de longitud $>N\cdot C$ y el uso de $N$ recortes para hacer $N$ cuerdas de longitud $C$.