Problema con el Jeep

El problema del jeep ^{[ 1 ]} , el problema de la travesía del desierto ^{[ 2 ]} o el problema de la exploración ^{[ 3 ]} es un problema matemático en el que un jeep debe maximizar la distancia que puede recorrer en un desierto con una cantidad de combustible determinada. El jeep solo puede transportar una cantidad fija y limitada de combustible, pero puede dejar y recoger combustible en depósitos ubicados en cualquier punto del desierto.

El problema apareció por primera vez en la colección del siglo IX Propositiones ad Acuendos Juvenes ( Problemas para agudizar a los jóvenes ), atribuida a Alcuino , donde el enigma trataba sobre un camello viajero que comía grano. ^{[ 4 ]} El De viribus quantitatis (c. 1500) de Luca Pacioli también aborda el problema. NJ Fine ofreció un tratamiento moderno en 1947. ^{[ 1 ]}

Hay n unidades de combustible almacenadas en una base fija. El jeep puede transportar como máximo 1 unidad de combustible en cualquier momento y puede recorrer 1 unidad de distancia con 1 unidad de combustible (se supone que el consumo de combustible del jeep es constante). En cualquier punto de un viaje, el jeep puede dejar cualquier cantidad de combustible que esté transportando en un depósito de combustible, o puede recoger cualquier cantidad de combustible que haya quedado en un depósito de combustible en un viaje anterior, siempre que su carga de combustible nunca supere 1 unidad. Hay dos variantes del problema:

• Explorando el desierto : el jeep debe regresar a la base al final de cada viaje. 
• Al cruzar el desierto , el jeep debe regresar a la base al final de cada viaje, excepto en el último, cuando recorre la mayor distancia posible antes de quedarse sin combustible. 

En ambos casos, el objetivo es maximizar la distancia recorrida por el jeep en su último viaje. Alternativamente, el objetivo puede ser encontrar la menor cantidad de combustible necesaria para realizar un último viaje de una distancia determinada.

Una estrategia que maximiza la distancia recorrida en el viaje final para la variante de "explorar el desierto" es la siguiente:

• El jeep realiza n viajes. En cada viaje parte de la base con 1 unidad de combustible.
• En el primer viaje, el jeep recorre una distancia de 1/(2 n ) unidades y deja ( n − 1)/ n unidades de combustible en un depósito. El jeep aún tiene 1/(2 n ) unidades de combustible , justo lo suficiente para regresar a la base.  
• En cada uno de los n − 1 viajes subsiguientes , el jeep recoge 1/(2 n ) unidades de combustible de este primer depósito a la ida, de modo que sale del depósito con 1 unidad de combustible. También recoge 1/(2 n ) unidades de combustible de este primer depósito a la vuelta, que es justo el combustible suficiente para regresar a la base.  
• En el segundo viaje, el jeep se dirige al primer depósito de combustible y reposta. Luego recorre una distancia de 1/(2 n − 2) unidades y deja ( n − 2)/( n − 1) unidades de combustible en un segundo depósito. El jeep aún tiene 1/(2 n − 2) unidades de combustible, lo justo para regresar al primer depósito. Allí recoge 1/(2 n ) unidades de combustible, lo justo para volver a la base.        
• En cada uno de los siguientes n − 2 viajes, el jeep recoge 1/(2 n − 2) unidades de combustible de este segundo depósito de combustible a la ida, de modo que sale del depósito con 1 unidad de combustible. También recoge 1/(2 n − 2) unidades de combustible del segundo depósito de combustible a la vuelta, lo cual es justo lo suficiente para regresar al primer depósito.      
• El jeep continúa de esta manera, de modo que en el viaje k establece un nuevo depósito de combustible k a una distancia de 1/(2 n − 2 k + 2) unidades del depósito anterior y deja allí ( n − k )/( n − k + 1) unidades de combustible. En cada uno de los n − k viajes subsiguientes recoge 1/(2 n − 2 k + 2) unidades de combustible del depósito k en su salida y otras 1/(2 n − 2 k + 2) unidades de combustible en su regreso.                    

Cuando el jeep inicia su viaje final, hay n − 1 depósitos de combustible. El más lejano contiene 1/2 de unidad de combustible, el siguiente más lejano contiene 1/3 de unidad de combustible, y así sucesivamente, y al depósito de combustible más cercano le quedan solo 1/ n unidades de combustible. Junto con 1 unidad de combustible con la que parte de la base, esto significa que el jeep puede recorrer una distancia total de ida y vuelta de  

${\displaystyle 1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}\equiv 2\times \mathrm {explore} (n)}$

unidades en su viaje final (la distancia máxima recorrida en el desierto es la mitad de esto). ^{[ 3 ]} Recoge la mitad del combustible restante en cada depósito en el camino de salida, lo que llena su tanque. Después de salir del depósito de combustible más lejano, viaja 1/2 unidad más adentro del desierto y luego regresa al depósito de combustible más lejano. Recoge el combustible restante de cada depósito de combustible en el camino de regreso, que es justo lo suficiente para llegar al siguiente depósito de combustible o, en el paso final, para regresar a la base.

La distancia recorrida en el último viaje es el enésimo armónico , H n _. Dado que los armónicos son ilimitados, es posible superar cualquier distancia en el viaje final, siempre que haya suficiente combustible en la base. Sin embargo, tanto la cantidad de combustible necesaria como el número de repostajes aumentan exponencialmente con la distancia a recorrer.

La variante de "cruzar el desierto" se puede resolver con una estrategia similar, excepto que ahora no hay requisito de recoger combustible en el viaje de regreso en el viaje final. Así que en el viaje k el jeep establece un nuevo depósito de combustible k a una distancia de 1/(2 n − 2 k + 1) unidades del depósito anterior y deja (2 n − 2 k − 1)/(2 n − 2 k + 1) unidades de combustible allí. En cada uno de los siguientes n − k − 1 viajes recoge 1/(2 n − 2 k + 1) unidades de combustible del depósito k en su salida y otras 1/(2 n − 2 k + 1) unidades de combustible en su regreso.                        

Ahora, cuando el jeep comienza su viaje final, hay n − 1 depósitos de combustible. El más lejano contiene 1/3 de unidad de combustible, el siguiente más lejano contiene 1/5 de unidad de combustible, y así sucesivamente, y al depósito de combustible más cercano le quedan solo 1/(2 n − 1) unidades de combustible. Junto con 1 unidad de combustible con la que comienza desde la base, esto significa que el jeep puede recorrer una distancia total de    

${\displaystyle 1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}\equiv \mathrm {cross} (n)}$

unidades en su viaje final. ^{[ 1 ] [ 3 ]} Recoge todo el combustible restante en cada depósito en el camino de salida, lo que llena su tanque. Después de salir del depósito de combustible más lejano, recorre una distancia adicional de 1  unidad.

Desde

${\displaystyle \mathrm {cross} (n)=\sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}=\mathrm {explore} (n)}$,

En teoría, es posible cruzar un desierto de cualquier tamaño con suficiente combustible en la base. Como antes, la cantidad de combustible necesaria y el número de repostajes aumentan exponencialmente con la distancia a recorrer.

En resumen, la distancia máxima que puede recorrer el jeep (con una capacidad de combustible para 1 unidad de distancia en cualquier momento) en n viajes (con n-1 repostajes intermedios y consumiendo un total de n unidades de combustible) es

• ${\displaystyle \mathrm {explorar} (n)={\frac {1}{2}}H_{n}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+\cdots +{\frac {1}{2n}}}$, para explorar el desierto donde el jeep debe regresar a la base al final de cada viaje;
• ${\displaystyle \mathrm {cross} (n)=H_{2n-1}-{\frac {1}{2}}H_{n-1}=1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}}$, para cruzar el desierto donde el jeep debe regresar a la base al final de cada viaje, excepto en el viaje final, cuando el jeep viaja tan lejos como puede antes de quedarse sin combustible.

Aquí${\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}$es el enésimo número armónico .

El problema puede tener una aplicación práctica en situaciones de guerra, especialmente en lo que respecta a la eficiencia del combustible . En el contexto del bombardeo de Japón en la Segunda Guerra Mundial por los B-29 , Robert McNamara dice en la película La niebla de la guerra que comprender el problema de la eficiencia del combustible causado por tener que transportar el combustible a las bases avanzadas fue la razón principal por la que se abandonó la estrategia de lanzar incursiones de bombardeo desde China continental en favor de la estrategia de salto de isla en isla : ^{[ 6 ]}

Teníamos que volar esos aviones desde las bases en Kansas hasta la India. Luego teníamos que volar combustible sobre el Himalaya hasta China. [...] Se suponía que debíamos usar esos B-29 ; allí no había aviones cisterna . Teníamos que llenarlos de combustible, volar desde la India hasta Chengtu ; descargar el combustible; volar de regreso a la India; realizar suficientes misiones para acumular combustible en Chengtu; volar a Yawata , Japón ; bombardear las acerías ; y regresar a la India.

Teníamos tan poca capacitación sobre cómo maximizar la eficiencia del combustible que, en lugar de descargar combustible de algunos B-29, tuvimos que cargarlo nosotros mismos. En resumen, no valía la pena. Fue LeMay quien llegó a esa conclusión y llevó a los jefes a trasladar todo el operativo a las Marianas , lo que devastó Japón.

(Las misiones de bombardeo atómico al final de la Segunda Guerra Mundial se llevaron a cabo utilizando bombarderos B-29 Superfortress desde la isla de Tinian, en las Islas Marianas del Norte, en el Pacífico ).

• Para comprender mejor la aplicación de estas ideas, consulte la Operación Black Buck . En estas misiones, llevadas a cabo durante la Guerra de las Malvinas , la Real Fuerza Aérea utilizó el reabastecimiento de combustible en vuelo mediante el despliegue de aviones cisterna para permitir que los bombarderos Vulcan , con base en la Isla Ascensión , bombardearan objetivos en las Islas Malvinas .
• Serie armónica (matemáticas)
• Optimización (matemáticas)