|
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 , é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 egy ilyen kút, a következő kút pedig legyen . Jelöljük a két kútban található üzemanyag mennyiségét -val, illetve -vel. Helyezzük át a -ben található üzemanyagot -ba, és a 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út, ahonnan indulva körbe lehet utazni. Azt állítjuk, hogy az eredeti és benzinkutak esetében is megfelelő. Induljunk el -ból. Amikor eljutunk -ba, az ott felvett üzemanyaggal biztosan eljutunk -be is, ott pedig felvesszük a üzemanyagot. elhagyásakor pontosan ugyanannyi üzemanyagunk lesz, mintha már -ban felvettük volna az üzemanyagmennyiséget; ezután pontosan ugyanaz történik, mint a módosított esetben. A 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 pontjában, ahonnan az egyik irányban nem juthatunk el a szomszédos kútig, ami -ben van. A kutakban levő üzemanyag mennyisége legyen és . Feltételezzük, hogy ; ellenkező esetben az és a szerepe felcserélhető. Jelölje azt a pontot, ameddig -ból felé elindulva az üzemanyaggal eljuthatunk. Csökkentsük le az üzemanyag mennyiségét az , illetve benzinkutakban -ra, illetve -ra, továbbá az ívet rövidítsük le az 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 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 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 -ból elindulunk valamelyik irányban, akkor előbb-utóbb eljutunk az iránytól függően -ba vagy -be; eddig a pontig nincs különbség a kétféle utazás között. Az vagy pontba érve az eredeti állapotban -val több üzemanyagot vehetünk fel, és az szakasz is éppen annyival hosszabb, amire ez a többlet üzemanyag elegendő. Az szakasz elhagyása után mindig -val több üzemanyagunk lesz, mint a lerövidített körön. A 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, -nál és -nél úgy, hogy a két kútban külön-külön ne legyen elegendő üzemanyag a hosszabbik ív megtételéhez. Ebben az esetben -ból csak pozitív, -ből csak negatív irányban járhatjuk be a kört.
|
|