Feladat:	A.245	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Csikvári Péter ,  Csóka Endre ,  Harangi Viktor ,  Horváth Illés ,  Jankó András ,  Kovács Erika Renáta ,  Kunszenti-Kovács Dávid ,  Tran Thanh Long ,  Varjú Péter ,  Vörös László
Füzet:	2001/március, 164 - 166. oldal		PDF  |  MathML
Témakör(ök):	Teljes indukció módszere, Szöveges feladatok, Matematikai logika, Nehéz feladat
Hivatkozás(ok):	Feladatok: 2000/október: A.245

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Előzetes megjegyzés. A klasszikusnak számító ,,benzinkutas feladatban'' azt kell igazolni, hogy ha a benzinkutakban található üzemanyag összesen legalább egy kör megtételére elegendő, akkor mindkét irányhoz létezik olyan benzinkút, amelyből indulva az autó körbeérhet. Ennek a feladatnak több érdekes megoldása is ismert; most csak egy egyszerű teljes indukciós bizonyítást mutatunk. A témáról részletesebben például Bizám György és Herczeg János Sokszínű logika c. könyvében olvashatunk. Legyen a körüljárás iránya rögzített; a megfelelő benzinkút létezését a benzinkutak száma szerinti indukcióval igazoljuk. Ha csak egyetlen benzinkút van, akkor ebben található az összes üzemanyag, amely a feltétel szerint legalább egy teljes kör megtételére elegendő, kész vagyunk. Legyen a benzinkutak száma $n$, és tegyük fel, hogy ennél kevesebb benzinkút esetén mindig létezik a megfelelő kiindulópont. A benzinkutak között lehetnek olyanok, amelyekből nem lehet a következő benzinkutat sem elérni; az ezekben levő üzemanyag mennyisége kevesebb, mint amennyi a soron következő útszakasz megtételéhez szükséges. Az ilyen benzinkutakban összesen biztosan kevesebb üzemanyag van, mint amennyi a teljes kör megtételéhez szükséges. Következésképpen van olyan benzinkút is, ahonnan el lehet érni a következő kutat. Legyen $A$ egy ilyen kút, a következő kút pedig legyen $B$. Jelöljük a két kútban található üzemanyag mennyiségét $a$-val, illetve $b$-vel. Helyezzük át a $B$-ben található üzemanyagot $A$-ba, és a $B$ kutat szüntessük meg (1. ábra). A benzinkutak száma csökkent, az indukciós feltevés szerint van tehát egy olyan $K$ kút, ahonnan indulva körbe lehet utazni. Azt állítjuk, hogy $K$ az eredeti $A$ és $B$ benzinkutak esetében is megfelelő. Induljunk el $K$-ból. Amikor eljutunk $A$-ba, az ott felvett $a$ üzemanyaggal biztosan eljutunk $B$-be is, ott pedig felvesszük a $b$ üzemanyagot. $B$ elhagyásakor pontosan ugyanannyi üzemanyagunk lesz, mintha már $A$-ban felvettük volna az $a+b$ üzemanyagmennyiséget; ezután pontosan ugyanaz történik, mint a módosított esetben. A $K$ kút tehát valóban megfelelő.   I. megoldás. Ismét a benzinkutak száma szerinti teljes indukcióval bizonyítunk. Egy kút esetén az állítás triviális. Ha mindegyik benzinkútban elég üzemanyag van ahhoz, hogy bármelyik irányban eljussunk a következő kútig, akkor bármelyik kúttól bármelyik irányban indulva biztosan körbeérünk. Feltehetjük tehát, hogy létezik egy kút a kör $A$ pontjában, ahonnan az egyik irányban nem juthatunk el a szomszédos kútig, ami $B$-ben van. A kutakban levő üzemanyag mennyisége legyen $a$ és $b$. Feltételezzük, hogy $a\le b$; ellenkező esetben az $A$ és a $B$ szerepe felcserélhető. Jelölje $C$ azt a pontot, ameddig $A$-ból $B$ felé elindulva az $a$ üzemanyaggal eljuthatunk. Csökkentsük le az üzemanyag mennyiségét az $A$, illetve $B$ benzinkutakban $0$-ra, illetve $\left(b-a\right)$-ra, továbbá az $AB$ ívet rövidítsük le az $AC$ távolsággal (2. ábra). Ekkor továbbra is kétszer annyi üzemanyag van, mint amennyi a (lerövidített) kör megtételéhez szükséges, viszont az $A$ benzinkút kiürítése révén a nem üres benzinkutak száma 1-gyel csökkent. Az indukciós feltevés szerint tehát létezik egy olyan $K$ benzinkút, ahonnan elindulva mindkét irányban körbehaladhatunk. Megmutatjuk, hogy ez a kút az eredeti körön is jó lesz. Ha $K$-ból elindulunk valamelyik irányban, akkor előbb-utóbb eljutunk az iránytól függően $A$-ba vagy $B$-be; eddig a pontig nincs különbség a kétféle utazás között. Az $A$ vagy $B$ pontba érve az eredeti állapotban $a$-val több üzemanyagot vehetünk fel, és az $AB$ szakasz is éppen annyival hosszabb, amire ez a többlet üzemanyag elegendő. Az $AB$ szakasz elhagyása után mindig $a$-val több üzemanyagunk lesz, mint a lerövidített körön. A $K$ kút tehát megfelelő.   II. megoldás. Nevezzük a két lehetséges irányt pozitívnak, illetve negatívnak. Tekintsük azokat a kutakat, amelyek ,,rosszak'' olyan értelemben, hogy onnan pozitív irányban elindulva nem érhetünk körbe. Ha az ezekben levő üzemanyag legalább egy kör megtételére elegendő, az a klasszikus feladat szerint ellentmondás; ha csak ezen kutak üzemanyagát használjuk fel, akkor is van olyan, ahonnan pozitív irányban körbeérhetünk. A kiválasztott kutakban található üzemanyag tehát kevesebb, mint amennyi egy teljes kör megtételéhez szükséges. Hasonlóan láthatjuk, hogy azokban a kutakban, ahonnan negatív irányban indulva nem érhetünk körbe, az egy kör megtételéhez szükségesnél kevesebb üzemanyag van. A rossz kutakban tehát összesen kevesebb üzemanyag van, mint amennyi két kör megtételéhez szükséges. Ezért a rossz kutak nem tartalmazhatják az összes üzemanyagot, van jó kút is.  Jankó András (Szeged, Ságvári E. Gyak. Gimn., 10. o.) dolgozata alapján   Megjegyzés. Ha a kutakban levő üzemanyag mennyisége nem elég két kör megtételére, akkor az állítás nem igaz. Helyezzük el a 3. ábra szerint az üzemanyagot két, egymáshoz közeli bezninkútnál, $A$-nál és $B$-nél úgy, hogy a két kútban külön-külön ne legyen elegendő üzemanyag a hosszabbik $AB$ ív megtételéhez. Ebben az esetben $A$-ból csak pozitív, $B$-ből csak negatív irányban járhatjuk be a kört.