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. A feladat szövege nem zárja ki azt a lehetőséget, hogy a segédautók (véges sokszor) visszatérjenek állomáshelyükre, benzint vegyenek fel, és újra visszatérjenek -hoz, vagy a többi, úton levő segédautóhoz. Ezt a lehetőséget ki is fogjuk használni a megoldásban. Válasszuk távolságegységnek azt az utat, amit egy tele tankkal induló autó ‐ további segítség nélkül ‐ meg tud tenni, eszerint a két város távolsága 2 egység. Jelöljük a városokat -vel és -vel, továbbá egy adott tervhez jelöljük -gal, illetve -gal a útszakasznak azt a -től, illetve -től legtávolabbi pontját, ameddig a -beli, illetve -beli segédautók a terv szerint eljutnak. Könnyen látható, hogy elegendő csak azokat a terveket vizsgálnunk, amelyek szerint tankja -ban tele van, és -ban üres. Ha -ben csak egy segédautót veszünk igénybe, akkor . Valóban, az utolsó fordulóban a segédautónak el kell mennie -ig, itt valamennyi benzint kell adnia -nak, és még vissza kell tudnia térni -be. Ez csak úgy lehetséges, ha a útszakasz kétszerese 1-nél kisebb, vagyis . Ugyancsak kisebb -nél a útszakasz hossza, ha -ben csak egy segédautót használunk, hiszen a -beli segédautónak el kell jutnia -ba, itt valamennyi benzint kell adnia -nak, és ezután vissza kell tudnia térni -be. Ezek szerint két segédautó nem elég, ha egyiket -ben, a másikat -ben használjuk. (Ennek bizonyításához az elmondottakon kívül csak azt kell még megjegyezni, hogy .) Akkor sem elég két segédautó, ha mind a kettőnek az állomáshelye. Legyen ugyanis az a pont, ahonnan az -t -ban feltöltő segédautó tele tankkal elindult, és az a pont, ahol feltöltése után, felé tartva kiürült a tankja. Az előbbiek szerint és kisebb -nél, és így , tehát két -beli segédautó valóban nem elég. Hasonlóan látható be, hogy nem elég két -beli segédautó sem.
Megmutatjuk, hogy három segédautó viszont már elegendő ahhoz, hogy -t -ből -be juttassuk el. Indítsuk el ugyanis -t -ből két segédautó kíséretével, és menjenek el együtt -ig, ahol . Itt az segédautó töltse tele tankját és menjen vissza -be, majd második fordulóban töltse tele ugyancsak -ban az segédautó tankját. Induljon tovább -ból az kíséretében, és tegyenek meg együtt ismét egységnyi utat. Ezután töltse tele az -t és térjen vissza -ba. Harmadik fordulóban jöjjön eléje idáig az segédautó -ből, így együtt már haza tudnak menni. Tehát a tervünk mellett . A pontból el tud jutni addig a pontig, melyre . Jöjjön eléje idáig -ből a harmadik, segédautó, innen együtt be tudnak menni -be. (Az ábra kis körgrafikonjai a tank tartalmát mutatják.)
Reviczky János (Budapest, I. István Gimn.) |
|