Pán František dostal možnosť zajazdiť si na okruhu F1. A na ozajstnej formule. Môže na nej prejsť celý jeden okruh.
Jeho snom bolo tiež odfotiť sa, ako do nej tankuje. Usporiadatelia tento jeho sen nepochopili úplne dobre. Vlastne ho nepochopili vôbec. Pozdĺž trate rozmiestnili barely s benzínom. V niektorých je benzínu viac, v iných menej. Dokopy je v nich benzínu akurát na prejdenie celej trate. Pán František dostane informáciu, koľko je barelov, kde sa nachádzajú a koľko je v každom benzínu (ako ďaleko sa s ním dostane).
Jeho formulu mu pristavia k barelu, ktorý si vyberie. Môže si natankovať (odfotia ho) a môže uháňať ďalej. Ak dôjde k ďalšiemu barelu, dotankuje si (zasa ho odfotia) a môže pokračovať.
A tak sa to bude opakovať až kým neprejde celú trať alebo mu nedôjde benzín medzi barelmi – v takom prípade končí.
Pán František chce samozrejme prejsť celý okruh a ešte viac chce fotky zo všetkých tankovaní. Preto sa troška strašne obáva, či je vždy šanca prejsť celý okruh, nech je ľubovoľný počet barelov s ľubovolným obsahom (dokopy na celý okruh), kdekoľvek umiestnených.
Je to jeho problém ale aj tak sú to zaujímavé otázky
Dá sa nájsť také rozmiestnenie a obsah barelov, že sa nebude dať prejsť celá trať?
Alebo sa dá dokázať, že sa vždy dá prejsť celá trať? V takom prípade by sa hodilo nájsť, ku ktorému barelu mu majú pristaviť formulu.
Prípadné straty paliva pri tankovaní alebo štartovaní sú v obsahu barelov zohľadnené. Nie je možné ušetriť benzín EKO jazdou. Jazdí sa iba v jednom smere.
Riešenie
Vyberieme si ľubovoľný barel a pozrieme kam by sme sa s ním dostali:
Krok 1) Skúmame, či by sme dostali k najbližšiemu barelu. Ak áno dotankujeme fiktívnu nádrž a zopakujeme tento bod. Ak takto “prejdeme” prejdeme celý okruh, tak je hotovo. Môžeme nakázať pristaviť formulu k barelu, s ktorým sme začali.
Krok 2) Čo ak zistíme, že by nám došiel benzín predtým ako “prejdeme” celý okruh? Napríklad, že by sme nedošli ani k druhému barelu, alebo že by sme prešli (dotankovali) niekoľko barelov ale potom by došiel benzín. V takom prípade sa vrátime sa ku kroku 1 s tým, že skúmame, kam by sme došli, ak by sme začali barelom ku ktorému sme nedošli. To sa samozrejme môže stať viackrát.
Nemôže sa stať, že by sme skúmanie napríklad začali barelom 1, prešli pár barelov a skončili pred barelom X a potom začali barelom X prešli cez posledný barel a nedošli k barelu 1. To by znamenalo, že sme minuli všetok benzín a neprešli sme celý okruh – a to sa nemôže stať, pretože benzín vystačí na celú trať.
Z rovnakého dôvodu sa nemôže stať, že by tých prerušení a nových štartov (t. j. “medzier”) bolo viac a my by sme skončili pred barelom 1.
Preto skôr, či neskôr začneme barelom, od ktorého prejdeme celý okruh – teda začneme ním a dôjdeme k nemu.
To je aj dôkaz, že sa to dá vždy prejsť.
Existuje aj iný veľmi pekný dôkaz, treba vedieť čítať graf a stačí si na chvíľku predstaviť, že môžeme jazdiť aj s nádržou, v ktorej je záporné množstvo benzínu. Ak to takto nakreslíme, vidíme, že začať treba pri najspodnejšom bode grafu, v tomto prípade na kilometri 2,6.
