Proyecto Euler pregunta 222

Question

Sería erróneo suponer que la solución a este problema:

¿Cuál es la longitud de la menor de la tubería, de radio interno de 50 mm, que pueden contener 21 de bolas de radios de 30 mm, 31 mm, ..., 50mm?

...consiste en el apilamiento de las bolas, desde el más grande al más pequeño, con cada bola en reposo en contra de la última alternando los lados de la tubería? Así:

Por lo tanto la reducción de esta a una relativamente sencillo geometría del problema. La razón que pido es porque mi solución a este acuerdo, se calcula en dos formas diferentes-no pasa; así que supongo que hay algún tipo de sutileza que me falta (es decir, hacer suposiciones falsas!).

Answer 1

He pasado algún tiempo en tratar de "demostrar" la '50, 30, 49, 31....' la configuración es correcta. Puede haber algunos puntos que me perdí.

Definir $H(x) = √[(100 – x)^2 – x^2] = … = 10 √(100 – 2x)$, que es por lo tanto una función decreciente. Deje $K(x) = H(50 – x) = 10√[2x]$ . Por lo tanto, es una función creciente.

Deje que el 21 de esferas ser etiquetados como $S_{50}, S_{49}, …, S_{30}$ donde $S_{50}$ es aquel cuyo radio = $R_{50} = 50$. El resto se define de forma similar. Las esferas son para ser colocado dentro de un tubo de radio $= 50$ de tal manera que se debe ocupar el menor longitud ($L$) de la tubería.

Los tamaños de las esferas no quiera que no cualquiera de los dos puede caber en el tubo de lado a lado.

Estrategia:- Coloque el más grande de la esfera ($S_{50}$ en este caso) en primer lugar, y seguido por $S_k$ donde $k = 49, 48, … , 30$.

La longitud requerida $= 50 + √[(50 + k)^2 – (100 – 50 – k)^2] + k$ ; $k = 49, 48, … , 30$ $= 50 + k + √[(100 – (50 – k))^2 – (50 – k)^2]$
$= 50 + k + 10√[100 – 2(50 – k)]$

$= 50 + k + 10√[2k]$

Longitud mínima ocupados $= 157.4596669$ ocurrió al $k = 30$.

Conclusión:- la Colocación de la más pequeña esfera en la parte superior de la más grande le dará un mejor uso de la tubería.

Después de lo anterior, el problema se reduce a uno que ha $19$ esferas, y son $S_k$; en caso de $k = 31, 32, …, 49$.* La estrategia se repite hasta que sólo tenemos una esfera (que es $S_{40}$) a la izquierda.

El apilamiento de una esfera sobre la otra, produce un pequeño aumento en la longitud, $X$, la cual está dada por:- $X = T – √[T^2 – (T – 100)^2]$; en caso de $T =$ la suma de los radios de las dos esferas.

{La derivación de $X$ puede ser encontrado en el Problema aquí.}

Utilizaremos $X_{v,u}$ para denotar la longitud adquirida por el apilamiento de $S_{v}$ en la parte superior de $S_{u}$.

• Por lo tanto, después de la etapa 1, el problema se reduce ahora a "dejar que el 19 de esferas ($S_{49}, S_{48}, …, S_{31}$) para el ajuste de la tubería; con el $S_{49}$ siendo el mayor pero con la parte inferior de ser aplanada". El proceso se repite hasta que .... Entonces L es dada por:-

$L = (S_{50}+S_{30} combination) + (S_{49}+S_{31} – X_{49,31}) + … + (S_{41}+S_{39} – X_{39,41}) +2*40 – X_{40,41}$

Si tal acuerdo es aceptado como el más óptimo, entonces L se puede encontrar también como:- $L = R_{50} + (R_{50} + R_{30} – X_{30,50}) + (R_{30} + R_{49} – X_{49,30}) + … + (R_{41} + R_{39} – X_{41,39}) + (R_{39} + R_{40} – X_{39,40}) + R_{40}$

= $2∑$$R_k$ – suma de los 20 extra longitudes adquirida por el apilamiento de las esferas

El ex suma es un AP, pero el último, por desgracia, es más bien irregular.

EDIT: El último comentario (sobre la suma es irregular) que hice (hace unos días), debería ser cambiado por el siguiente motivo:-

Deje $X_{v,u} = T_{v,u} – √[T_{v,u}^2 – (T – 100)^2]$; en caso de $T_{v,u} =$ (la suma de los radios de $S_v$$S_u) = v + u$.

A continuación, $X_{v,u} = … = (v + u) – √[200(v + u) – 100^2]$

Tenga en cuenta que:- $X_{30,50} = X_{31,49} = … = X_{39,41} = {80 – √[200(80) – 100^2]} = 80 – √6000$

Del mismo modo, $X_{49,30} = X_{48,31} = … = X_{40,39} = {79 – √[200(79) – 100^2]} = 79 – √5800$

Suma de los $20$ extra de longitudes adquirida por el apilamiento de las esferas $= X_{30,50} + X_{49,30} + X_{31,49} + X_{48,31} + X_{32,48} + … + X_{38,42} + X_{41,38} + X_{39,41} + X_{40,39}$

= $[X_{30,50} + X_{31,49} + X_{32,48} + … + X_{38,42} + X_{39,41}] +[X_{49,30} + X_{48,31} + … + X_{41,38} + X_{40,39}]$

$= 10 × [80 – √6000] + 10 × [79 – √5800]$

$= 53.826xxx$

$L = 1680 - 53.826xxx = 1626.173xxx$

El de arriba es sólo para el cálculo de la longitud ocupada por el $S_{50} + S_{30} + S_{49} + ... $ configuración. Tal configuración puede que no la configuración óptima. Estoy trabajando en otra disposición posible.

Answer 2

En relación a mi anterior post, sugiero el siguiente como una mejor configuración.

Continuando con el post anterior, tenemos

$X_{v,u} =$ Extra de longitud adquirida al apilar $S_v$ a $S_u$

$= (T) – √[200(T) – 100^2]$; en caso de $T = v + u$ = la suma de los dos radios

$L = 2∑R_k–∑X_i$ (donde $R_k$ es el radio de la $k$-ésimo de la esfera y de $i = 1, 2, …,20$.)

A continuación, $Min(L) = Min(2∑R_k –∑X_i)$ $= 2∑R_k– Max(∑X_i ) = 2∑R_k– Y$ (decir)

Por lo tanto, con el fin de encontrar Min(L), es suficiente para encontrar la más grande de las Y diferentes configuraciones.

Antes de continuar, nos diversa un poco para señalar que $F(T) = T – √(200T–100^2)$ es una función decreciente en el intervalo de $[61, 99]$.

[La prueba, que consiste en la proyección de $F'(T) < 0$, es bastante estricto adelante y se omite.]

La disminución de la función ofrece las siguientes sugerencias para el mejor método de apilado:-

1. "Poner a las dos más pequeñas esferas adyacentes el uno del otro dará una ganancia más grande en X." \begin{array}{ll} n2^{n}\left(x - n + \frac{1}{2^{n}} \right)& \textrm{if } x \in \left[ n - \frac{1}{2^{n}}, n\right]\\[0.5em] n2^{n}\left(n + \frac{1}{2^{n}} - x \right) & \textrm{if } x \in \left[ n, n + \frac{1}{2^{n}}\right]\\[0.5em] 0 & \textrm{otherwise} \end(*)

2. "Poner a las dos grandes esferas adyacentes el uno del otro dará una menor ganancia en X." ----(#)

Primero vamos a echar un vistazo a la versión simplificada de la situación de tener sólo 3 esferas ($S_{30}$, $S_{49}$, y $S_{50}$)

Debemos considerar los siguientes 3 casos sólo:-

El más grande en el medio-----$Y(S_{30}, S_{50}, S_{49}) = 2.54538371$

El medio en el medio---$Y(S_{30}, S_{49}, S_{50}) = 2.8473196$

El más pequeño en el medio---$Y(S_{50}, S_{30}, S_{49}) = 5.38260202$

A partir de esto, nuestra observación es

"Poniendo la más pequeña entre los dos mayores tendrá una mejor ganancia en longitud." ----(@)

Esto también se puede comprobar matemáticamente como:-

$Y(S_{50}, S_{30}, S_{49}) – Y$(otras combinaciones)

$= Y(S_{50}, S_{30}, S_{49}) – Y(S_{30}, S_{49}, S_{50})$; [por ejemplo]

$= (X_{49,30}+ X_{30,50}) – [X_{50,49} + X_{49,30}]$

$= X_{30,50} – X_{50,49}$

$= [80–√[200(80)–100^2] – [99–√[200(99)–100^2]$

$ > 0$ (desde $F(T)$ es una función decreciente.)

A continuación, considere el caso de tener sólo 4 esferas (2 más grande ($S_{50}$ & $S_{49})$ + 2 más pequeño $(S_{30}$ & $S_{31})$.

Caso 1. Colocando el más grande de los dos uno al lado del otro

----$Y(S_{30} + S_{49} + S_{50} + S_{31}) = … = 5.10724084 =$ la longitud obtenida es demasiado pequeño

----$Y(S_{50} + S_{49} + S_{31} + S_{30}) = … = 16.6412261$

Caso 2. Par (Una pequeña y una grande)

--- $Y(S_{31} + S_{49} + S_{30} + S_{50}) = … = 7.92293509 = $de la longitud obtenida es demasiado pequeño

--- $Y(S_{30} + S_{49} + S_{50} + S_{31}) = … =$ de la longitud obtenida es demasiado pequeño (como case1(i))

Caso 3. Colocando el más pequeño de los dos uno al lado del otro

--- $Y(S_{50} + S_{31} + S_{30} + S_{49}) = … = 19.1980326$

--- $Y(S_{50} + S_{30} + S_{31} + S_{49}) = … = 19.176509$

--- $Y(S_{50} + S_{49} + S_{31} + S_{30}) = … = 16.xxxxx$ (como case1(ii))

Esto muestra que el $S_{50} + S_{31} + S_{30} + S_{49}$ combinación tiene un mejor uso de la tubería. En realidad, todas estas cifras además, se verificó la exactitud de ( * ), número (#) y también (@). Y también nos dan otra pista:-

"El más grande de los dos esferas deben ser colocados en los extremos (uno en cada extremo del tubo." ----(%)

Sumando estas arriba, propongo la siguiente configuración:-

$(S_{50}+S_{48}+ … +S_{40}+S_{38}+S_{36}+ … +S_{32})+S_{30}+[S_{31}+S_{33}+ … +S_{47}+S_{49}]$

La correspondiente longitud extra ganó $= 89.06688385$

$Min(L) = 1590.933116$, [una cifra mucho menor que el $S_{50}+S_{30}+S_{49}+S_{31}+ ...$ configuración.]

Answer 3

Esto no es una respuesta pero es una buena manera de verlo:

Vamos a llamar a nuestra bola "ciudades"

Y las distancias

A la tubería que tenemos,

Cuando se apilan, "caminos"

¿Lo que tenemos?

 

¡Un viajante! Para este problema específico, tal vez nosotros podemos optimizar la búsqueda, pero algoritmos modernos ya son capaces de resolverlo.