Enanos en un puente

Question

300 empequeñece ir sobre un puente en medio de la noche. El puente es raquítico y llega a a lo más dos enanos a la vez. Con ellos es una linterna que debe proporcionar en cada transición. Enanos necesitan tiempo diferentes para el puente: 1min, 2min, 3min... y 300 minutos. Cuando dos enanos, van con el más lento de la velocidad. Ningún enano quiere ir sobre el puente de más de 3 veces (es decir, frente-atrás-adelante). ¿Qué es el tiempo mínimo que puede gestionar la transición?

Answer 1

Supongamos que tenemos $n$ enanos y deje $x_i$ ser el momento en el $i$th cruce enano tiene que cruzar el puente. Tenga en cuenta que cualquier par de enviar el principio, es mejor regresar a la más rápida de los enanos. Por lo tanto, el total de tiempo de cruce es igual a $$\max\{x_1,x_2\} + \min\{x_1,x_2\} + \sum_{i=3}^{n-1}x_i + \sum_{i=2}^{n-1}\max\{x_i,x_{i+1}\},$$ que es igual a (asumiendo $x_1>x_2$) $$\sum_{i=1}^{n-1}x_i + \sum_{i=2}^{n-1}\max\{x_i,x_{i+1}\},$$ A continuación, vamos a arreglar el enano en lugar de $n$ y ver que es mejor tener enano 1 el más lento de los restantes enano, ya que el cambio de enano 1 con enanos $k<n$ tal que $x_k>x_2$ eleva el total de tiempo de cruce por $$\begin{align} \max\{x_{k-1},x_1\} + \max\{x_1,x_{k+1}\} &- \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} = \\ 2x_1 &- \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} > 0. \end{align}$$ Del mismo modo, dado que arreglemos el enano $1$ su mejor tener enano n el más lento de los restantes enano, ya que el cambio de enanos $n$ con enanos $k$ eleva el total de tiempo de cruce por $$\begin{align} x_n-x_k + \max\{x_{k-1},x_n\} + \max\{x_n,x_{k+1}\} - \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} - (\max\{x_{n-1},x_n\} - \max\{x_{n-1},x_k\}) = \\ 2x_n - \max\{x_{k-1},x_k\} - \max\{x_k,x_{k+1}\} + \max\{x_{n-1},x_k\} - x_k > 0. \end{align}$$ Llegamos a la conclusión de que $x_1$ $x_n$ tienen que ser los dos más lento de los enanos. Esto significa que tenemos que encontrar una orden de enanos $2,\ldots,n-1$ que minimiza $$\sum_{i=1}^{n}x_i + \sum_{i=2}^{n-2}\max\{x_i,x_{i+1}\},$$ lo que equivale a la minimización de $$\sum_{i=2}^{n-2}\max\{x_i,x_{i+1}\}.$$ Ver por ti mismo que esto se hace por orden de los $x_i$ desde cualquiera de los de más rápido a más lento, o más lento al más rápido.

Llegamos a la conclusión de que el mínimo de tiempo es igual a $$\begin{align} \sum_{i=1}^{300}i + \sum_{i=2}^{298}\max\{x_i,x_{i+1}\} &= \sum_{i=1}^{300}i + \sum_{i=2}^{298}i \\ &= 2\sum_{i=1}^{300}i - 1-299-300 \\ &= 2\frac{300(300+1)}{2} - 600 \\ &= 300^2 - 300 \end{align}$$ Tenga en cuenta que hemos encontrado cuatro soluciones únicas para que este mínimo es alcanzado.

Answer 2

Sugerencia: Si dos pase y uno se vuelve, la dejas un enano en el otro extremo y la linterna en el extremo cercano. ¿Cuántos viajes requiere que todos los 300 enanos cruzar el puente? Hay una leve perturbación al final. ¿Cuántos tienen que volver? Claramente desea los más rápidos vuelve.

Answer 3

De acuerdo a lo que yo creo es la misma manera de resolver un puente similar cruce problema, se comienza con los dos mejores personas corriendo por el puente.

Entonces uno de ellos se ejecuta de nuevo para volver a la lámpara.

Los dos más lento cruzar el puente siguiente. Mediante el envío de los 2 más lento, minimalize el tiempo perdido por ellos.

Una vez que se cruzaron, el otro chico (uno de los rápidos) se ejecuta de nuevo con la lámpara.

Los dos corredores más rápidos distinta de la original de 2 ir a la siguiente. Repetimos este proceso, con los 2 más lento caminar a través de juntos y más rápido corriendo hacia atrás y adelante.

Haremos esto hasta 100 lento enanos han hecho de todo.

Ahora tenemos 200 enanos a la izquierda.

Los 100 más rápidos, ya cruzó el puente dos veces, así que esta tercera carrera será el último.

Pero alguien debe ser capaz de llevar la lámpara de vuelta!

Por lo tanto, hacer parejas entre la actual 66 más lento de los corredores y 66 corredores más rápidos.

Van a encontrarse, después de que la lentitud de los corredores de retorno de la lámpara de nuevo.

Repita esto hasta que todos los 66 corredores más rápidos de hacer su última vuelta.

Ahora estamos a la izquierda con 68 de los enanos.

El truco era tomar la forma más rápida de 1/3 y más lento de 1/3, permitiendo que el medio de 1/3 a llevar lámparas de vuelta en el final.