Problém džípu ( angl. Jeep problem, desert crossing problem, exploration problem ) je matematický problém, jehož cílem je maximalizovat vzdálenost, kterou může ujet auto s plnou nádrží paliva při absenci infrastruktury, např. poušť.
Celková kapacita kanystrů a plynové nádrže džípu je 100 litrů, spotřeba paliva je konstantní číslo, například na 1 sekci se spotřebuje 1 litr. Množství paliva na základně není omezeno. Můžete provést další dvě akce: vypustit část paliva kdekoli v poušti (na kterémkoli místě v poušti může být sud s palivem, ve kterém můžete po neomezenou dobu ponechat neomezenou část paliva) a také vzít nějaké palivo. paliva z barelu, který již nějaké množství paliva obsahoval. Tento problém má dvě varianty: problém průzkumu pouště a problém přechodu pouště. V prvním případě je cílem návrat na základnu (ve výchozí poloze), ve druhém stačí překonat úsek větší, než umožňuje zásoba paliva.
Jak je uvedeno výše, problém s Jeepem má dvě varianty: problém průzkumu a problém přejezdu pouště. Podívejme se na každou z nich.
Strategie, která pomáhá prodloužit vzdálenost, kterou může džíp urazit v problému průzkumu pouště, je:
Když džíp jede naposledy, je tam n − 1 barelů paliva. Poslední sud má 1/2 množství paliva, předposlední 1/3 a tak dále, dokud první sud nemá 1/ n množství paliva. Vzhledem k tomu, že na výjezdu ze základny má džíp plnou zásobu paliva, celkem může urazit vzdálenost
Vzdálenost ujetá džípem při poslední cestě je n-té harmonické číslo - H n . Vzhledem k tomu, že harmonické číslo může narůstat donekonečna, délka dráhy, kterou může džíp urazit, může být také nekonečná, za předpokladu, že je na základně dostatek paliva, ale počet barelů na doplnění paliva poroste exponenciálně.
Řešení problému s přejezdem pouště je podobné řešení problému s průzkumem pouště, až na to, že při poslední cestě není potřeba tankovat na zpáteční cestě. Při k - té cestě opustí džíp k -tý sud ve vzdálenosti 1/(2 n − 2 k + 1) od předchozí zastávky a odjede (2 n − 2 k − 1)/(2 n − 2 k + 1) palivo . Pro každou z dalších n − k − 1 jízd džíp natankuje 1/(2 n − 2 k + 1) množství paliva na k -té zastávce při jízdě vpřed a zpět.
Když džíp jede naposledy, je tam n − 1 barelů paliva. Poslední má 1/3 paliva, předposlední 1/5 a tak dále, nejbližší má 1/(2 n − 1) množství paliva. V tomto případě může džíp projet
Všimněte si, že
to znamená, že je teoreticky možné překonat poušť jakékoli velikosti, s dostatkem paliva na základně. Stejně jako v předchozím problému roste množství paliva potřebného k tomu exponenciálně.