O problema do jipe,^[1] problema de travessia do deserto^[2] ou problema de exploração^[3] é um problema matemático em que um jipe deve maximizar a distância que pode percorrer num deserto com uma determinada quantidade de combustível. O jipe só pode carregar uma quantidade fixa e limitada de combustível, mas pode deixar combustível e coletar combustível em depósitos de combustível localizados em qualquer lugar do deserto.

O problema apareceu pela primeira vez na coletânea do século IX Propositiones ad Acuendos Juvenes (Problemas para Aguçar os Jovens), atribuída a Alcuíno, na qual o enigma tratava de um camelo viajante comendo grãos.^[4] A obra De viribus quantitatis (c. 1500) de Luca Pacioli também discute o problema. Uma abordagem moderna foi dada por N. J. Fine em 1947.^[1]

Existem n unidades de combustível armazenadas numa base fixa. O jipe pode carregar no máximo 1 unidade de combustível a qualquer momento, e pode percorrer 1 unidade de distância com 1 unidade de combustível (assume-se que o consumo de combustível do jipe seja constante). Em qualquer ponto de uma viagem, o jipe pode deixar qualquer quantidade de combustível que estiver carregando num depósito de combustível, ou pode coletar qualquer quantidade de combustível que tenha sido deixada num depósito de combustível numa viagem anterior, desde que a sua carga de combustível nunca exceda 1 unidade. Existem duas variantes do problema:

• Explorando o deserto — o jipe deve regressar à base no final de cada viagem.
• Atravessando o deserto — o jipe deve regressar à base no final de cada viagem, exceto na última viagem, quando o jipe viaja o mais longe que consegue antes de ficar sem combustível.

Em ambos os casos, o objetivo é maximizar a distância percorrida pelo jipe na sua viagem final. Em alternativa, o objetivo pode ser encontrar a menor quantidade de combustível necessária para realizar uma viagem final de uma determinada distância.

No problema clássico, o combustível no jipe e nos depósitos de combustível é tratado como uma quantidade contínua. Foram propostas variações mais complexas do problema nas quais o combustível só pode ser deixado ou recolhido em quantidades discretas.^[5]

Uma estratégia que maximiza a distância percorrida na viagem final para a variante "explorando o deserto" é a seguinte:

• O jipe faz n viagens. Em cada viagem, ele parte da base com 1 unidade de combustível.
• Na primeira viagem, o jipe percorre uma distância de ${\displaystyle 1/(2n)}$ unidades e deixa ${\displaystyle (n-1)/n}$ unidades de combustível em um depósito de combustível. O jipe ainda tem ${\displaystyle 1/(2n)}$ unidades de combustível — apenas o suficiente para regressar à base.
• Em cada uma das ${\displaystyle n-1}$ viagens subsequentes, o jipe recolhe ${\displaystyle 1/(2n)}$ unidades de combustível deste primeiro depósito de combustível na ida, de modo a deixar o depósito de combustível carregando 1 unidade de combustível. Ele também recolhe ${\displaystyle 1/(2n)}$ unidades de combustível deste primeiro depósito de combustível no trajeto de volta, o que corresponde ao combustível exato para regressar à base.
• Na segunda viagem, o jipe viaja até o primeiro depósito de combustível e reabastece. Em seguida, percorre uma distância de ${\displaystyle 1/(2n-2)}$ unidades e deixa ${\displaystyle (n-2)/(n-1)}$ unidades de combustível em um segundo depósito de combustível. O jipe ainda possui ${\displaystyle 1/(2n-2)}$ unidades de combustível, que é o necessário para retornar ao primeiro depósito de combustível. Aqui ele recolhe ${\displaystyle 1/(2n)}$ unidades de combustível, a quantidade exata para regressar à base.
• Em cada uma das ${\displaystyle n-2}$ viagens seguintes, o jipe recolhe ${\displaystyle 1/(2n-2)}$ unidades de combustível deste segundo depósito de combustível na ida, de modo que ele saia do depósito de combustível com 1 unidade de combustível. Ele também retira ${\displaystyle 1/(2n-2)}$ unidades de combustível do segundo depósito de combustível na volta, o que é apenas o combustível suficiente para regressar ao primeiro depósito de combustível.
• O jipe continua desta forma, de modo que na viagem k ele estabelece um novo k-ésimo depósito de combustível a uma distância de ${\displaystyle 1/(2n-2k+2)}$ unidades do depósito de combustível anterior e deixa ${\displaystyle (n-k)/(n-k+1)}$ unidades de combustível lá. Em cada uma das ${\displaystyle n-k}$ viagens seguintes, ele recolhe ${\displaystyle 1/(2n-2k+2)}$ unidades de combustível do k-ésimo depósito na sua ida e outras ${\displaystyle 1/(2n-2k+2)}$ unidades de combustível na sua volta.

Quando o jipe inicia sua última viagem, existem ${\displaystyle n-1}$ depósitos de combustível. O mais distante contém 1/2 de uma unidade de combustível, o segundo mais distante contém 1/3 de uma unidade de combustível e assim por diante, com o depósito de combustível mais próximo tendo apenas ${\displaystyle 1/n}$ unidades de combustível sobrando. Juntamente com 1 unidade de combustível com a qual ele parte da base, isto significa que o jipe pode percorrer uma distância total de ida e volta 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 na sua viagem final (a distância máxima percorrida pelo deserto é metade disto).^[3] Ele recolhe metade do combustível restante em cada depósito no caminho de ida, o que enche o seu tanque. Depois de deixar o depósito de combustível mais distante, ele viaja mais 1/2 unidade para o deserto e, em seguida, retorna ao depósito de combustível mais distante. Ele recolhe o combustível remanescente de cada depósito de combustível na volta, o que é o estritamente necessário para alcançar o próximo depósito de combustível ou, na etapa final, regressar à base.

A distância percorrida na última viagem é o n-ésimo número harmônico, H_n. Como os números harmônicos não são limitados, é possível exceder qualquer distância determinada na viagem final, desde que haja combustível suficiente disponível na base. No entanto, a quantidade de combustível exigida e o número de depósitos de combustível aumentam exponencialmente em função da distância a ser percorrida.

A variante "atravessando o deserto" pode ser solucionada com uma estratégia semelhante, exceto pelo fato de que agora não há a obrigação de coletar combustível no caminho de volta da última viagem. Assim, na viagem k o jipe estabelece um novo k-ésimo depósito de combustível a uma distância de ${\displaystyle 1/(2n-2k+1)}$ unidades do depósito de combustível anterior e deixa ${\displaystyle (2n-2k-1)/(2n-2k+1)}$ unidades de combustível lá. Em cada uma das ${\displaystyle n-k-1}$ viagens seguintes ele retira ${\displaystyle 1/(2n-2k+1)}$ unidades de combustível do k-ésimo depósito na sua ida e outra porção de ${\displaystyle 1/(2n-2k+1)}$ unidades de combustível na sua volta.

Agora, quando o jipe começa a sua viagem derradeira, há ${\displaystyle n-1}$ depósitos de combustível. O mais afastado possui 1/3 de uma unidade de combustível, o segundo mais distante possui 1/5 de uma unidade de combustível e assim sucessivamente, com o depósito de combustível mais perto contando com somente ${\displaystyle 1/(2n-1)}$ unidades de combustível sobrando. Junto com 1 unidade de combustível com a qual ele sai da base, isto significa que o jipe pode percorrer uma distância 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 em sua viagem final.^[1][3] Ele recolhe todo o combustível restante em cada depósito na ida, o que preenche o seu tanque. Ao deixar o depósito de combustível mais distante, ele viaja uma distância extra de 1 unidade.

Como

${\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)}$,

é teoricamente viável atravessar um deserto de qualquer tamanho se houver combustível suficiente na base. Tal como anteriormente, a quantidade de combustível necessária e o número de depósitos de combustível sobem exponencialmente com a distância a ser percorrida.

Resumindo, a distância máxima alcançável pelo jipe (com uma capacidade de combustível de 1 unidade de distância a qualquer momento) em n viagens (com ${\displaystyle n-1}$ depósitos intermediários de combustível e consumindo um total de n unidades de combustível) é

• ${\displaystyle \mathrm {explore} (n)={\frac {1}{2}}H_{n}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+\cdots +{\frac {1}{2n}}}$, para explorar o deserto onde o jipe deve regressar à base no final de cada viagem;
• ${\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 atravessar o deserto onde o jipe deve regressar à base no final de cada viagem, exceto na última, quando o jipe viaja o mais longe possível antes de ficar sem combustível.

Aqui, ${\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}$ é o n-ésimo número harmônico.

A quantidade de unidades de combustível disponíveis na base não necessita ser um número inteiro. No caso geral, a distância máxima atingível no problema de "explorar o deserto" com ${\displaystyle n}$ unidades de combustível é

${\displaystyle \mathrm {explore} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil n-f\rceil }}}$

com o primeiro depósito de combustível alocado a ${\displaystyle \{n\}/(2\lceil n\rceil )}$ unidades de distância da base inicial, o segundo a ${\displaystyle 1/(2\lceil n\rceil -2)}$ unidades de distância do primeiro depósito de combustível, o terceiro a ${\displaystyle 1/(2\lceil n\rceil -4)}$ unidades de distância do segundo depósito de combustível e assim sucessivamente. Aqui ${\displaystyle \{n\}=n-\lfloor n\rfloor }$ é a parte fracionária de ${\displaystyle n}$.

A distância máxima que pode ser alcançada para o problema de "atravessar o deserto" com ${\displaystyle n}$ unidades de combustível é

${\displaystyle \mathrm {cross} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil n-f\rceil -1}}}$

com o primeiro depósito de combustível situado a ${\displaystyle \{n\}/(2\lceil n\rceil -1)}$ unidades de distância da base inicial, o segundo a ${\displaystyle 1/(2\lceil n\rceil -3)}$ unidades de distância do primeiro depósito de combustível, o terceiro a ${\displaystyle 1/(2\lceil n\rceil -5)}$ unidades de distância do segundo depósito de combustível e assim sucessivamente. Aqui ${\displaystyle \{n\}=n-\lfloor n\rfloor }$ é a parte fracionária de ${\displaystyle n}$.

A ordem das viagens de jipe não é estática. Por exemplo, na versão "explorando o deserto" do problema, o jipe poderia fazer ${\displaystyle n-1}$ viagens de ida e volta entre a base e o primeiro depósito de combustível, alocando ${\displaystyle (n-1)/n}$ unidades de combustível no depósito de combustível a cada vez e então efetuar uma ${\displaystyle n}$-ésima viagem só de ida para o primeiro depósito de combustível, chegando lá assim com um total de ${\displaystyle (n-1)+1/(2n)}$ unidades de combustível acessíveis. As ${\displaystyle 1/(2n)}$ unidades são poupadas para a viagem de volta à base no final de tudo e as outras ${\displaystyle n-1}$ unidades de combustível são utilizadas para transportar combustível do primeiro ao segundo depósito de combustível, por meio de ${\displaystyle n-2}$ viagens de ida e volta e então fazer uma ${\displaystyle (n-1)}$-ésima viagem só de ida para o segundo depósito de combustível. E dessa forma em diante.

O problema pode ter uma aplicação concreta em contextos de guerra, mormente com respeito à eficiência do combustível. Na conjuntura do bombardeio do Japão na Segunda Guerra Mundial por aeronaves B-29, Robert McNamara afirma no filme The Fog of War que a compreensão do entrave da eficiência de combustível desencadeado por ter de levar o combustível para bases avançadas foi a motivação capital do porquê a estratégia de iniciar ataques de bombardeio da China continental ter sido preterida a favor da tática de salto de ilhas:^[6] Citação: Tínhamos que pilotar aqueles aviões das bases do Kansas para a Índia. Em seguida, tínhamos que transportar combustível sobre o corcovado [Himalaia] até a China. [...] Nós devíamos pegar esses B-29s — não havia aeronaves de reabastecimento lá. Devíamos enchê-los de combustível, voar da Índia para Chengtu; descarregar o combustível; voar de volta para a Índia; fazer missões suficientes para acumular combustível em Chengtu; voar para Yawata, no Japão; bombardear as usinas siderúrgicas; e regressar para a Índia.

Tínhamos recebido tão pouco treinamento para lidar com a questão de maximizar a eficiência [do combustível] que percebemos que, para trazer alguns B-29 de volta em vez de descarregar combustível, eles tinham que abastecer. Para resumir a história, não servia para nada. E foi LeMay quem realmente concluiu isso e fez com que os Chefes de Estado-Maior transferissem a operação toda para as ilhas Marianas, o que aniquilou o Japão.

(As missões do bombardeio atômico no término da Segunda Guerra Mundial foram efetuadas usando os B-29 Superfortresses a partir da ilha do Pacífico de Tinian, nas Ilhas Marianas do Norte.)

• Leia Operação Black Buck para entender melhor a aplicação dessas ideias. Nessas missões, realizadas durante a Guerra das Malvinas, a Força Aérea Real (RAF) empregou o reabastecimento aéreo através de aviões-tanque escalonados para permitir que os bombardeiros Vulcan sediados na Ilha de Ascensão bombardeassem alvos nas Ilhas Malvinas.
• Série harmônica (matemática)
• Otimização (matemática)