Dar la vuelta al mundo en avión

Question

Estoy interesado en una generalización del siguiente acertijo:

Eres el director de un aeropuerto situado en el ecuador, y cada avión de tu aeropuerto puede tener suficiente combustible para volar por medio mundo. Tus aviones también pueden reunirse en el aire para compartir el combustible. Tu tarea es utilizar el menor número de aviones posible para dar la vuelta al mundo con éxito, pero todos los aviones que utilices deben aterrizar con seguridad en tu aeropuerto. ¿Cuántos aviones necesitas?

La respuesta al acertijo es $3$ (puedes intentar averiguar esto, o hacer una búsqueda rápida en Internet para encontrar una solución).

Aquí está mi formulación de una generalización, que todavía tengo que resolver y que me encantaría que la comunidad de aquí pensara.

Dejemos que $n$ sea el número de aviones en su aeropuerto. ¿Cuál es la distancia mínima $d(n)$ cada avión puede volar con el depósito lleno (medido en proporción a la distancia total alrededor del mundo) para asegurar que es posible volar con éxito un avión alrededor del mundo con todos los aviones aterrizando con seguridad en su aeropuerto?

Esto es lo que creo saber hasta ahora. Si $n=1$ necesitamos que el único avión pueda dar la vuelta al mundo, así que $d(1)=1$ . Si no he cometido ningún error, entonces creo que $d(2)=\frac{3}{5}$ . También creo que $d(3)=\frac{1}{2}$ o, en otras palabras, el acertijo original es "agudo" en algún sentido. No lo sé. $d(n)$ para $n\ge 4$ pero tengo razones para creer que

$$\lim_{n\to\infty}d(n)=\frac{1}{4}$$

por lo que si nuestros aviones pueden dar una cuarta parte de la vuelta al mundo (o menos) con el depósito lleno, no tenemos ninguna esperanza de dar una vuelta al mundo por muchos aviones que tengamos.

Dejo fuera intencionadamente la justificación de esta información sobre $d(n)$ porque no quiero contaminar el pensamiento de otra persona, y me gustaría tener una confirmación independiente.

Para un mayor desafío, también se podría definir $f(D,n)$ para ser la cantidad total máxima de combustible "sobrante" entre $n$ aviones que pueden recorrer una distancia $D$ con el depósito lleno tras haber volado con éxito un avión alrededor del mundo. La intuición podría sugerir que $f(d(n),n)=0$ (es decir, si nos sobra combustible al final de los vuelos, nuestros aviones deben poder volar una distancia mayor de la necesaria), pero no creo que esto sea cierto. De hecho, creo que $f(\frac{1}{2},3)=\frac{1}{4}$ Es decir, hay una solución al acertijo original en la que los aviones quedarán con suficiente combustible para seguir volando un avión una cuarta parte de la vuelta al mundo.

Tengo más cosas que decir, pero voy a terminar aquí porque la pregunta ya es bastante larga. Tal vez dentro de unos días, después de dar tiempo a la comunidad para pensar, y si mis resultados no se han verificado (o se ha demostrado que son incorrectos), publicaré mi justificación.

---

Adición: Como señala Fimpellizieri más abajo, debería indicar que estoy suponiendo que todos los aviones viajan a la misma velocidad constante en todo momento. El final de su respuesta ofrece una solución mejor para el caso $n=3$ si no hacemos estas suposiciones y nos libramos de las limitaciones de tiempo. Este problema sin tiempo también es muy interesante para mí.

Además, me gustaría señalar que esta pregunta (que desconocía cuando lo publiqué originalmente) y sus respuestas son relevantes. En particular, las respuestas de Brian Trial afirman que $d(8)\le \frac{1}{3}$ y proporcionan una gran manera de visualizar gráficamente los viajes de los aviones.

Answer 1

Esto no es exactamente una respuesta, sino más bien reflexiones sobre el problema. Tal vez alguien pueda encontrar otro enfoque.

Para $d = d(3)$ Considere la siguiente estrategia, separada en dos partes.

---

Parte ( $\mathbf 1$ ):

• $P_1, P_2$ y $P_3$ saldrán del aeropuerto en el sentido de las agujas del reloj. $P_3$ será el avión que haga el viaje de ida y vuelta.

• $P_1$ volará $r$ distancia, reembolsar cada uno de los otros dos planos para $r$ distancia, y volver otra $r$ distancia al aeropuerto.

• $P_2$ por lo tanto, tendrá combustible para un total de $d+r$ distancia a su disposición. Escribimos $d+r =$ $x+ y + u$ , indicando que:

  • $P_2$ junto con $P_3$ , volará $x$ distancia del aeropuerto en el sentido de las agujas del reloj.
  • En este punto, $P_2$ donará $y$ combustible a $P_3$ .
  • $P_2$ volará de vuelta $u$ distancia, llegando a una distancia de $x-u$ desde el aeropuerto sin combustible.

• $P_3$ por lo tanto, tendrá combustible para un total de $d+r+y$ distancia a su disposición.

• Después de repostar en el aeropuerto, $P_1$ volará el $x-u$ distancia hacia $P_2$ y devolverlo por $x-u$ distancia. Ambos se dirigirán juntos al aeropuerto.

A partir de esto, debemos tener

• $0\leqslant r\leqslant d/4$ : $P_1$ puede volar $r$ distancia hacia adelante y hacia atrás, y reembolsar cada otro plano $r$ distancia
• $x\geqslant r$ : $P_2$ debe volar al menos $r$ distancia al aeropuerto
• $0\leqslant y \leqslant x- r$ El combustible donado no puede ser negativo ni superar $P_3$ La capacidad del tanque
• $0\leqslant u\leqslant x$ : $P_2$ no puede retroceder una distancia negativa y no puede retroceder más de lo que voló hacia adelante
• $2\cdot r + (x-u) \leqslant x+u$ : $P_2$ no debe quedarse sin combustible antes de $P_1$ puede alcanzarlo de nuevo
• $x-u \leqslant d/3$ : $P_1$ puede alcanzar $P_2$ y los dos tendrán suficiente combustible para volver al aeropuerto.

Poniendo todo junto, las condiciones que tenemos hasta ahora son

$$\left\{\begin{array}{ccccc} d + r &=& x+y+u&&\\ 0&\leqslant &r &\leqslant& d/4 \\ r &\leqslant& x &\leqslant & u + d/3\\ 0&\leqslant &y &\leqslant& x-r\\ 0&\leqslant &u &\leqslant& x\\ r&\leqslant &u \end{array}\right.$$

En esta parte, tenemos que

• $P_1$ cubre un total de $2\,r+ 2\,(x-u)$ distancia.
• $P_2$ cubre un total de $2x$ distancia.
• $P_3$ cubre un total de $d+ r + y$ distancia.

---

Parte ( $\mathbf 2$ ):

• Aviones $P_1$ y $P_2$ saldrán del aeropuerto en sentido contrario a las agujas del reloj para reunirse y repostar $P_3$ .

• $P_1$ volará $s$ distancia, reembolso $P_2$ para $s$ distancia, y volver otra $s$ distancia al aeropuerto.

• $P_2$ por lo tanto, tendrá combustible para un total de $d+s$ distancia a su disposición. Escribimos $d+s =$ $\big[1-(d+r+y)\big] + 2z$ , lo que indica que

  • $P_2$ volará $\big[1-(d+r+y)\big]$ distancia del aeropuerto en dirección contraria a las agujas del reloj para reunirse con $P_3$ .
  • En este punto, $P_2$ donará $z$ combustible a $P_3$ .
  • $P_2$ y $P_3$ entonces ambos volarán de vuelta $z$ distancia, llegando a una distancia de $1-d-r-y-z$ desde el aeropuerto sin combustible.

• Después de repostar en el aeropuerto, $P_1$ volará la distancia hacia $P_2$ y $P_3$ y reembolsar a cada uno de ellos esa cantidad de combustible. Los tres aviones volverán juntos al aeropuerto.

A partir de esto, debemos tener

• $0 \leqslant s\leqslant d/3$ : $P_1$ puede volar $s$ distancia hacia adelante y hacia atrás, y reembolso $P_2$ para $s$ distancia
• $z\geqslant 0$ no puede donar combustible negativo
• $2x + 1-d-r-y \leqslant d+r+y$ : $P_3$ no debe quedarse sin combustible antes de $P_2$ puede alcanzarlo de nuevo
• $1-d-r-y - z \leqslant d/4$ : $P_1$ puede alcanzar $P_2$ y $P_3$ y los tres tendrán suficiente combustible para volver al aeropuerto.
• $2x + 2s + 1-d-r-y - z\leqslant d+r+y + z$ : $P_2$ y $P_3$ no debe quedarse sin combustible antes de $P_1$ puede llegar a ellos de nuevo

Juntando todo esto:

$$\left\{\begin{array}{ccccc} 2d+s+r+y &=& 1 + 2z&&\\ 0&\leqslant& s&\leqslant&d/3\\ z&\geqslant& 0&&\\ x+1/2&\leqslant& d+r+y&&\\ 1 &\leqslant& 5d/4 + r + y + z&&\\ x + s + 1/2&\leqslant &d + r + y + z&& \end{array}\right.$$

---

Podríamos esperar que tal vez alguna solución a esto con $d<1/2$ podría existir, pero parece que no es así. De hecho, ya si consideramos el subsistema

$$\left\{\begin{array}{ccc} 2d+s+r+y &=& 1 + 2z\\ y &\leqslant& x-r\\ x + 1/2 &\leqslant& d + r + y\\ 1 &\leqslant& 5d/4 + r + y + z\\ x + s + 1/2 &\leqslant& d + r + y + z\\ d&<&1/2 \end{array}\right.$$

Wolfram Alpha indica que no existen soluciones. Aunque no es una prueba definitiva, esto significa que para que $d(3) < 1/2$ Hay que utilizar una estrategia totalmente diferente.

---

Si los aviones pudieran frenar o acelerar (quemando el mismo combustible por distancia), entonces se podrían descartar algunas desigualdades (las que se refieren a que los aviones se queden sin combustible antes de que otro pueda alcanzarlo). Obtendríamos el siguiente sistema

$$\left\{\begin{array}{ccccc} d + r &=& x+y+u&&\\ 2d+s+r+y &=& 1 + 2z&&\\ \\ 0&\leqslant &r &\leqslant& d/4 \\ 0&\leqslant& s&\leqslant&d/3\\ r &\leqslant& x &\leqslant & u + d/3\\ 0&\leqslant &y &\leqslant& x-r\\ 0&\leqslant &u &\leqslant& x\\ 0&\leqslant& z&&\\ 1 &\leqslant& 5d/4 + r + y + z&& \end{array}\right.$$

Puede comprobar que lo siguiente es una solución con $d<1/2$ :

$$\left\{\begin{array}{ccc} d&=&9/20\\ r&=&9/80\\ x&=&11/40\\ y&=&13/80\\ u&=&1/8\\ s&=&3/20\\ z&=&13/80 \end{array}\right.$$

Answer 2

Se trata de una variante del Problema con el Jeep en la versión de la travesía del desierto. Si sigues la solución de la travesía del desierto, el último jeep llega lo más lejos posible y luego se encuentra con los aviones que vienen por el otro lado para llevarlo a casa. Si $d$ es la autonomía de un vehículo con el depósito lleno y $D(n)$ es la distancia desde la base a la que se encuentra el último vehículo de $n$ puede salir con el depósito lleno, necesita $d+2D(n)$ para ser la circunferencia del mundo. Es de suponer que, al ser aviones, queman combustible mientras holgazanean, por lo que necesitamos $n$ aviones para despegar para replicar $n$ unidades de combustible en la base en el problema estándar donde se puede almacenar el combustible.

Utilizando la información del artículo de Wikipedia, para $d=1$ podemos manejar una circunferencia de $2(H_{2n-1}-\frac 12H_{n-1})-1$ para $n$ avión en el que $H_k$ es el $k^{th}$ Número armónico $H_k=\sum_{i=1}^k\frac 1i\approx \log k+\gamma$ .

Hice el problema de Jeep donde el avión tiene que volver en esta respuesta.

Answer 3

No veo ningún límite inferior para $d(n)$ . Por ejemplo, esta es una solución para $d(n)= \frac{1}{4}$ utilizando la técnica de visualización de Brian Trial (los números mostrados son el número de aviones que se mueven en esa dirección):

Supongamos que cada avión tiene una capacidad de depósito de $3$ unidades de combustible (lo que significa que se necesitaría $12$ unidades de combustible para dar la vuelta al mundo). En la figura anterior, la distancia al aeropuerto se indica en unidades de combustible.

En la figura, un avión que se aleja del aeropuerto, siempre tendrá el depósito lleno en su nodo de partida. Un avión que se mueve hacia el aeropuerto siempre tendrá $\frac{1}{3}$ tanque.

El principio es el siguiente:

Un avión que se aleja del aeropuerto utiliza $1$ unidad de combustible para llegar desde su nodo actual al siguiente. Cuando llega al siguiente nodo, el avión hace una de las siguientes cosas:

1. Reabastece de combustible a un avión que regresa con $1$ unidad de combustible y se dirige al aeropuerto con $1$ unidad de combustible en su depósito.
2. Reabastece de combustible a un avión hermano (haciendo el mismo movimiento de nodo) con $1$ unidad de combustible y se dirige al aeropuerto con $1$ unidad de combustible en su depósito.
3. Se reabastece con $1$ unidad de combustible por un avión hermano y continúa alejándose del aeropuerto con el depósito lleno.

Un avión que se desplaza hacia el aeropuerto sólo hace una cosa: repostar con $1$ unidad de combustible por un avión que llega del aeropuerto y sigue hacia el aeropuerto.

Observando la figura, el número máximo de aviones en el aire en cualquier momento es $172$ Así que $d(172) \le \frac{1}{4}$ .

El procedimiento anterior debería ser aplicable a cualquier $d(n)$ por lo que veo.

Hazme saber si me he equivocado.