¿La estrategia óptima para cortar una salchicha?

Question

Eres un estudiante, asignado a trabajar en la cafetería hoy, y es tu deber repartir la comida disponible entre todos los estudiantes. La comida de hoy es una salchicha de 1 m de longitud, y tienes que cortarla en tantos trozos como alumnos vengan a comer, incluido tú.

El problema es que el cuchillo se acciona con la puerta giratoria por la que entran los alumnos, por lo que cada vez que entra un alumno, el cuchillo baja y tú colocas el corte. No hay forma de que sepas si vendrán más estudiantes o no, así que después de cada corte, la salchicha debe ser cortada en trozos de aproximadamente la misma longitud.

Así que aquí la pregunta - ¿es posible colocar los cortes de manera que la relación entre la pieza más grande y la más pequeña sea siempre inferior a 2?

Y si es así, ¿cuál es la menor proporción posible?

Ejemplo 1 (la unidad es el cm):

• Primer corte: 50 : 50 proporción: 1
• 2º corte: 50 : 25 : 25 proporción: 2 - malo

Ejemplo 2

• 1er corte: Relación 40 : 60: 1,5
• 2º corte: 40 : 30 : 30 relación: 1.33
• Tercer corte: 20 : 20 : 30 : 30 proporción: 1,5
• 4º corte: 20 : 20 : 30 : 15 : 15 proporción: 2 - malo

Perdón por la horrible analogía, creo que se trata de un problema matemático, pero no tengo ni idea de cómo formularlo de forma matemática.

Answer 1

TLDR: $a_n=\log_2(1+1/n)$ funciona, y es la única solución suave.

Este problema sugiere una cuestión matemática más profunda, como la siguiente. Como ha observado Pongrácz, hay una gran cantidad de variaciones posibles en las soluciones a este problema. Me gustaría encontrar la "mejor" solución, en la que la secuencia de piezas esté distribuida de la manera más uniforme posible, dadas las restricciones.

Fijemos la siguiente estrategia: en la etapa $n$ hay $n$ piezas, de longitudes $a_n,\dots,a_{2n-1}$ ordenados de forma decreciente. Se corta $a_n$ en dos trozos, formando $a_{2n}$ y $a_{2n+1}$ . Tenemos las siguientes restricciones:

$$a_1=1\qquad a_n=a_{2n}+a_{2n+1}\qquad a_n\ge a_{n+1}\qquad a_n<2a_{2n-1}$$

Me gustaría encontrar una buena función $f(x)$ que interpola todos estos $a_n$ s (y posiblemente generaliza la relación $a_n=a_{2n}+a_{2n+1}$ también).

En primer lugar, está claro que el único grado de libertad está en la elección del corte, es decir, si tomamos cualquier secuencia $b_n\in (1/2,1)$ entonces podemos definir $a_{2n}=a_nb_n$ y $a_{2n+1}=a_n(1-b_n)$ y esto definirá completamente la secuencia $a_n$ .

Ahora deberíamos esperar que $a_n$ es asintótica a $1/n$ ya que se reduce en un factor de $2$ cada vez $n$ dobles. Así, una condición de regularidad que podemos imponer es que $na_n$ converge. Si consideramos la "solución base" en la que cada corte está en $1/2$ produciendo la secuencia

$$1,\frac12,\frac12,\frac14,\frac14,\frac14,\frac14,\frac18,\frac18,\frac18,\frac18,\frac18,\frac18,\frac18,\frac18,\dots$$ (que no es técnicamente una solución debido a la desigualdad estricta, pero está en el límite de las soluciones), entonces vemos que $na_n$ de hecho lo hace no tienden a un límite - varía entre $1$ y $2$ .

Si promediamos esto exponencialmente, considerando la función $g(x)=2^xa_{\lfloor 2^x\rfloor}$ entonces obtenemos una función que se acerca cada vez más a ser periódica con periodo $1$ . Es decir, existe una función $h(x):[0,1]\to\Bbb R$ tal que $g(x+n)\to h(x)$ y necesitamos que esta función sea constante si queremos $g(x)$ mismo para tener un límite.

Existe una relación muy directa entre $h(x)$ y el $b_n$ s. Si aumentamos $b_1$ dejando todo lo demás igual, entonces $h(x)$ se ampliará en $[0,\log_2 (3/2)]$ y se redujo en $[\log_2 (3/2),1]$ . Ninguno de los otros $b_i$ controlan este equilibrio izquierda-derecha - hacen $h(x)$ mayor en alguna subregión de uno u otro de estos intervalos solamente, pero conservando $\int_0^{\log_2(3/2)}h(x)\,dx$ y $\int_{\log_2(3/2)}^1h(x)\,dx$ .

Por lo tanto, para mantenerlas equilibradas debemos dejar que $b_1=\log_2(3/2)$ . En general, cada $b_n$ controla el equilibrio de $h$ en los intervalos $[\log_2(2n),\log_2(2n+1)]$ y $[\log_2(2n+1),\log_2(2n+2)]$ (reducido $\bmod 1$ ), por lo que debemos establecerlos en $$b_n=\frac{\log_2(2n+1)-\log_2(2n)}{\log_2(2n+2)-\log_2(2n)}=\frac{\log(1+1/2n)}{\log(1+1/n)}.$$

Cuando hacemos esto, se produce un milagro, y $a_n=\log_2(1+1/n)$ se resuelve analíticamente: \begin {align} a_1&= \log_2 (1+1/1)=1 \\ a_{2n}+a_{2n+1}&= \log_2\Big (1+ \frac1 {2n} \Big )+ \log_2\Big (1+ \frac1 {2n+1} \Big ) \\ &= \log_2\left [ \Big (1+ \frac1 {2n} \Big ) \Big (1+ \frac1 {2n+1} \Big ) \right ] \\ &= \log_2\left [1+ \frac {2n+(2n+1)+1}{2n(2n+1)} \right ] \\ &= \log_2\left [1+ \frac1n\right ]=a_n. \end {align}

Como ventaja, obviamente tenemos que el $a_n$ es decreciente, y si $m<2n$ entonces \begin {align} 2a_m&=2 \log_2\Big (1+ \frac1m\Big )= \log_2\Big (1+ \frac1m\Big )^2= \log_2\Big (1+ \frac2m + \frac1 {m^2} \Big ) \\ & \ge\log_2\Big (1+ \frac2m\Big )> \log_2\Big (1+ \frac2 {2n} \Big )=a_n, \end {align}

por lo que se trata efectivamente de una solución adecuada, y además hemos alcanzado nuestro objetivo de suavidad - $na_n$ converge, a $\frac 1{\log 2}=\log_2e$ . También cabe destacar que la diferencia entre la pieza más grande y la más pequeña tiene límite exactamente $2$ que valida la observación de Henning Makholm de que no se puede hacer nada mejor que $2$ en el límite.

El aspecto es el siguiente (redondeado a la centena más cercana, por lo que los números pueden no sumar 100 exactamente):

• $58:42$ , ratio = $1.41$
• $42:32:26$ , ratio = $1.58$
• $32:26:22:19$ , ratio = $1.67$
• $26:22:19:17:15$ , ratio = $1.73$
• $22:19:17:15:14:13$ , ratio = $1.77$

Si se trabaja con una secuencia de puntos tratados $\bmod 1$ donde los intervalos entre los puntos son las "salchichas", entonces esta secuencia de segmentos es generada por $p_n=\log_2(2n+1)\bmod 1$ . El resultado es bellamente uniforme pero con un notable borde de barrido:

                                  

Una condición de optimalidad más concreta que recoge esta solución de forma única es la siguiente: requerimos que para cualquier fracción $0\le x\le 1$ La salchicha en el $x$ posición (más o menos una salchicha) en la lista, ordenada de forma decreciente, debe ser como máximo $c(x)$ veces menor que el mayor en todo momento. Con esta solución se consigue $c(x)=x+1$ para todos $0\le x\le 1$ y ninguna solución puede hacerlo mejor (en el límite) para cualquier $x$ .

Answer 2

SÍ, es posible.

No debes cortar una pieza por la mitad, porque eventualmente tienes que cortar una de ellas, y entonces violas el requisito. Así que, de hecho, nunca debes tener dos partes iguales. Haz el primer corte para que no se viole la condición, digamos $60:40$ .

A partir de ahora, supongamos que la relación entre el mayor y el menor es estrictamente inferior a $2$ en una ronda determinada, y no hay dos piezas iguales. (Esto es válido para el $60:40$ corte). Construimos un buen corte que mantiene esta propiedad.

Así que en el siguiente turno, escoge la pieza más grande, y córtala en dos trozos no iguales en un $a:b$ pero muy cerca de la igualdad (por lo que $a/b\approx 1$ ). Lo único que hay que asegurarse es que

• $a/b$ está tan cerca de $1$ que las dos nuevas piezas son más pequeñas que la pieza más pequeña de la última ronda.
• $a/b$ está tan cerca de $1$ que la pieza más pequeña es más grande que la mitad de la segunda más grande de la última ronda (que se convertirá en la pieza más grande de esta ronda).

Entonces la condición se mantiene. Por ejemplo, desde $60:40$ puede pasar a $25:35:40$ y luego cortar los cuarenta para obtener $19:21:25:35$ etc.

Answer 3

No se puede hacer mejor que un factor de $2$ .

Supongamos, por el contrario, que tiene una estrategia tal que la relación entre la pieza mayor y la menor que queda es siempre $<R$ para algunos $R<2$ .

Entonces, primero podemos ver que para cada $\varepsilon>0$ finalmente habrá dos piezas cuya relación sea como máximo $1+\varepsilon$ . De lo contrario, la relación entre la pieza más grande y la más pequeña sería como mínimo $(1+\varepsilon)^n$ que finalmente supera $R$ .

Una vez que tenga dos piezas de longitud $a$ y $b$ con $a < b < (1+\varepsilon)a$ eventualmente tendrás que cortar uno de ellos.

Si se corta $a$ primero, una de las piezas será como máximo $\frac12 a < \frac12b$ Así que su objetivo ha fracasado inmediatamente.

Sin embargo, si se corta $b$ primero, una de las piezas será como máximo $\frac12b < \frac{1+\varepsilon}2 a$ , lo que significa que has perdido si elegimos $\varepsilon$ sea lo suficientemente pequeño como para que $\frac{1+\varepsilon}2 < \frac1R$ . Y eso siempre es posible si $R<2$ .