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. Az alábbi feladatot az 1980. évi Országos Középiskolai Tanulmányi Verseny II. fordulóján a matematika II. tagozatú osztályok számára tűzték ki: Egy sivatagi expedíciónak a sivatag szélén levő táborból egy liter vizet kell eljuttatnia a sivatagnak olyan pontjára, amely napi járásra van az expedíció táborától. A szállítást úgy kell megszervezni, hogy a) az expedíció tagjai sohasem vihetnek magukkal fejenként 3 liternél több ivóvizet; b) a sivatagban töltött minden nap folyamán az expedíció valamennyi tagjának meg kell innia egy‐egy liter vizet; c) feladatuk teljesítése után az expedíció valamennyi tagjának vissza kell térnie a táborba. Legalább hány liter ivóvíznek kell lennie a táborban, hogy teljesíthet legyen a kitűzött feladat? Ebben a cikkben a feladat megoldásairól lesz szó. Azért beszélünk megoldásokról és nem a megoldásról, mert a szövegből nem derül ki pontosan, hogy mik is azok a feltételek, amelyek mellett a sivatagba az egy liter vizet el kell juttatni. A különböző lehetséges értelmezések különböző végeredményekhez vezetnek, a megoldandó feladat nehézsége is más‐más. A verseny résztvevői között nem akadt olyan, aki a feladat szövegéhez talán legszorosabban kapcsolódó ‐ általunk harmadikként tárgyalandó ‐változatot oldotta volna meg. A második változat egy dolgozatban szerepelt, míg a döntő többség véleménye szerint a feladatot úgy kell értelmezni, ahogyan az az első változatban szerepel. Mielőtt a feladat megoldásához érdemben hozzálátnánk, néhány megjegyzést teszünk. Először is feltesszük, hogy azok, akik egész nap a táborban maradnak, nem isznak vizet, vagy legalábbis az általuk elfogyasztott vízmennyiség nem tartozik a meghatározandó készlethez. Másodszor, feltehetjük, hogy az expedíció tagjai a sivatagban csak a célt a táborral összekötő szakasz mentén mozognak, továbbá ‐ mivel ezt egyik feltétel sem tiltja ‐ útjuk mentén tetszőleges helyen tetszőleges mennyiségű vizet felhalmozhatnak A b) feltétel szerint az expedíció tagjai minden a sivatagban töltött nap folyamán egy liter vizet isznak meg. Az azonban nem derül ki, hogy azoknak is jár-e az 1 liter víz, akik nem egész napot töltenek a sivatagban. Feltesszük, hogy igen, vagyis a b) feltételt a következő feltétellel helyettesítjük: b') a sivatagban töltött minden megkezdett napra az expedíció tagjainak jár egy-egy liter víz. Végül feltesszük azt is, hogy az expedíciónak elég sok tagja van, vagyis ha új embert kell bevetnünk, akkor mindig akad pihent tartalék. Első változat Bemelegítésként vizsgáljuk meg, hogyan tudják az expedíció tagjai a kitűzött feladatot megoldani kis értékei mellett. esetén 1 nap járóföldre kell 1 liter vizet eljuttatnunk. Ehhez elég 1 ember és 3 liter víz: az ember reggel elindul a 3 liter vízzel a kulacsában; délben megiszik 1 litert, este megérkezik a célhoz. Ott leteszi a nála levő 2 liter víz felét. Másnap visszaindul, útközben megissza a kulacsban maradt 1 litert, estére visszaérkezik a táborba. Ezzel a feladatot megoldotta, s nyilván ehhez 3 liternél kevesebb víz nem elég. Legyen most . Világos, hogy a célhoz csak egy ember megy el ‐ a szükséges 1 liter vizet egyedül is el tudja vinni. Ez pedig azt jelenti, hogy a tábortól egy napi járóföldre levő pontból teli kulaccsal ‐ 3 liter vízzel ‐ kell elindulnia a cél felé (1. ábra). Azonban még ha a táborból teli kulaccsal indult is, útközben 1 litert megivott! A hiányt -ben pótolnia kell. Másrészt mikor -ből jövet visszaérkezik -be, kulacsa egészen üres, s hogy szomjan ne haljon és a tábor között, -ben újabb liter víznek kell várnia. Így -be még két liter vizet kell eljuttatnunk. Ehhez -ból két embert kell indítanunk (nem feltétlenül egyszerre) tele kulaccsal. -ig megisznak 1‐1 litert, ott letesznek 1‐1 litert, s visszamennek a táborba a megmaradt 1‐1 liter vizükkel.
1. ábra Összesen három kulacsot kellett tele töltenünk, vagyis a felhasznált vízmennyiség liter. Ha , akkor az előzőhöz hasonlóan 2 l vizet kell eljuttatnunk az 1 napi járóföldre levő pontba, s 2 litert -be is. Ha ez már megtörtént, akkor az expedíció egy tagja induljon el a táborból tele kulaccsal. Mire -be ér, kulacsából 1 liter hiányozni fog, de ezt a -ben található 2 liter vízből pótolja. Most továbbindul -be, ott ismét pótolja a és között elfogyasztott vizet. -ből teli kulaccsal indul a cél, felé. Ott letesz 1 litert, mire visszaérkezik -be minden vize elfogyott. A -ben maradt 1 liter vízzel visszamegy -be, az ottani vízzel pedig szerencsésen visszaérkezik a táborba. Nézzük ehhez mennyi vízre van szükség ! -be 1 liter vizet ‐ az előzőek szerint ‐ 9 literből, -be pedig 3 literből tudunk eljuttatni, így kell liter. Azt sejthetjük, hogy ha a táborban liter víz van, akkor a feltételeknek megfelelően 1 litert el tudunk juttatni napi járóföldre. Láttuk, hogy ez esetében valóban így is van, s tegyük fel, hogy mellett ezt már beláttuk. napi járóföldre 1 liter vizet ‐ az előbbiekkel analóg módon ‐ úgy juttathatunk el, hogy először egy napi, 2 napi, , napi járóföldre 2‐2 litert vitetünk (ehhez a táborban literre van szükség). Ezután egyetlen ember teli kulaccsal nekivág a sivatagnak. Minden nap végén pótolni tudja az aznap elfogyasztott vízmennyiséget egészen a -edik nap végéig, onnan elvisz 1 litert a napi járóföldre levő pontba, majd visszafelé is minden nap este megtalálja a következő napra szükséges 1 literét. A felhasznált vízmennyiség | | liter, tehát az állítás mellett is igaz. A teljes indukció elve alapján a sejtésünket ‐ vagyis, hogy liter víz elegendő ahhoz, hogy napi járóföldre 1 liter vizet eljuttassunk ‐ bizonyítottuk. Az eljárást követve a literből a pontba összesen liter jut el, a -be liter, általában az napi járóföldre levő pontba liter. Az is könnyen látható, hogy és között az expedíciónak összesen tagja fordult meg (mindenkit annyiszor számítva, ahányszor belépett ebbe az intervallumba), mégpedig ezek fele -ből -be, a másik fele -ből felé tartott. Az expedíció tagjainak indulását úgy is megszervezhetjük, hogy egyáltalán ne kelljen vizet tárolni a sivatagban. A 2. ábrán egy ilyen ütemezést mutatunk be -ra.
2. ábra Azt is sejthetjük, hogy ez a liter víz nemcsak elegendő a feladat végrehajtásához, hanem szükséges is: hogyan is tudnánk megtakarítani akár egy cseppet is? Vannak sejtések, melyek igazak, s vannak melyek nem. Sajnos ez a sejtésünk az utóbbi csoportba tartozik: már esetén sincs szükség 9 literre. A feladat 6 liter vízből is megoldható például a következő módon (3. ábra).
3. ábra Az expedíció egyik tagja induljon el egy teli kulaccsal. Fél napi járóföldre a tábortól igyon meg egy liter vizet. A kulacsot a megmaradt két literrel tegye le, és menjen vissza a táborba. Összesen egy napot töltött a sivatagban, s az erre az időre járó 1 liter vizet el is fogyasztotta. Fél napi menetelés után abból a kulacsból, amit kollégája az előző nap ott hagyott, megiszik 1 liter vizet, s továbbmegy. Estére az egy napi járóföldre levő pontba jut. Innen másnap reggel 3 liter vízzel indul tovább -be, ott letesz 1 litert, s üres kulaccsal érkezik vissza -be. A tábor és között félúton még egy liter víz vár rá, így emberünk baj nélkül jut vissza a táborba. A 3 liter víz megtakarítását az tette lehetővé, hogy az expedíció első tagja fél napi járóföld után fordult vissza. Bár első pillanatban úgy érezzük, ezt nem teheti meg, a feltételeket újra végigolvasva láthatjuk, hogy azok ezt nem tiltják. Ennek ellenére a legtöbb megoldó úgy érezte, hogy a következő megszorítás lappangva ott bújkál a feladat szövegében: d) az expedíció tagjai napközben nem állhatnak meg és nem fordulhatnak vissza,
és természetesen mindenki ugyanakkora utat tesz meg egy nap alatt. Megmutatjuk, két különböző módon is, hogy e feltétel mellett a liter vízre szükség is van. Tegyük fel tehát, hogy az a)‐d) feltételek mellett sikerült az expedíció tagjainak a feladatukat végrehajtani. Jelöljük a tábortól napi járóföldre levő pontot -vel , a pontba vagy azon túl eljutó vízmennyiségét -vel, és -vel az expedíció azon tagjainak számát, akik -ből felé elindultak, mindenkit annyiszor számolva, ahányszor -et elhagyta. A d) feltétel szerint ezek mindegyike eljutott -be, s mivel mindenkinek végül vissza kell jutnia a táborba, azért -ből vissza -be is pontosan tagja ment az expedíciónak. Az mennyiség definíciójában azért kellett ilyen óvatosan fogalmaznunk, mert az expedíció bármely tagja ,,ingázhat" a pontok között, s ugyanazt a utat sokszor megteheti. Ha a szállítást az expedíció tagjai úgy szervezik, ahogyan azt korábban leírtuk, akkor (hiszen -be összesen ennyi víz jut el) és . Tudjuk, hogy mindegyik nem-negatív, (ez a feladat), és azt szeretnénk megmutatni, hogy . Nézzük, mit tudunk! -ből felé összesen alkalommal indultak el, visszafelé is ugyanennyien jöttek, tehát a két pont között liter víz fogyott el (4. ábra).
4. ábra Ezt a litert, továbbá azt a litert, amelynek -be kell jutnia, az darab, -ből -be tartó út alkalmával el kell tudni szállítani -ből. Tehát egyrészt másrészt hiszen legalább liter víznek el kell hagynia a pontot. A feltétel alapján ( napi járóföldre legalább 1 liter vizet kell eljuttatni), (1)-ből adódik majd (2)-ből . Ismét (1)-ből , (2)-ből pedig . Hasonlóan továbbmenve végül is azt kapjuk, hogy , ahogyan kívántuk. A másik bizonyítás alapötlete a következő. A vizet a sivatag egy távolabbi pontjára nehezebb bevinni, mint egy közelebbire, ezért ott a víz étékesebb. Mondjuk 1 liter víznek az értéke a táborban , a tábortól napi járóföldre peg . Ha a számokat ügyesen választjuk, akkor elérhetjük, hogy az expedíció tevékenysége folyamán a még meglevő, a sivatagban és a táborban valahogyan szétosztott víz összértéke ne nőjön. S ha még ezt úgy is meg tudjuk csinálni, hogy legyen, akkor készen vagyunk : az expedíció tevékenységének befejezésekor a víz értéke legalább (hiszen van 1 liter, értékű víz napi járóföldre), ezért kezdetben is legalább ilyen értékű víznek kellett a táborban lennie. Ám a táborban 1 liter víz értéke csak 1, azért ez éppen liter vizet jelent. Az ötlet kivitelezéséhez még egy észrevételre van szükségünk. Ha az expedíció egy tagja a sivatagban tartózkodik, akkor ezzel csökkenti az ott található víz értékét, hiszen ebből a vízből kell fedezni a táborba való visszajutáshoz szükséges mennyiséget. Ezek után lássuk az értékelést. Tegyük fel, hogy vége van egy napnak, vagyis az expedíció minden tagja valamelyik pontban ( egész, tartózkodik. Jelölje a -ben tartózkodó emberek számát, pedig azt, hogy -ben, valamint és között együttvéve hány liter víz van. Ehhez az állapothoz a következő értéket rendeljük: | | (3) | Állítjuk, hogy ez az érték nem nő. Ebből már következik, hogy az expedíció feladatának végrehajtásához legalább liter vízre szükség van. Kezdetben ugyanis és kivételével az összes többi és érték 0. A feladat végrehajtása után kivételével az összes értéke 0 ‐ ez jelenti azt, hogy mindenki visszatért a táborba ‐, és ezért , továbbá és minden -re. A (3) által definiált érték nem nőtt, ezért | | amiből valóban következik, hogy . Így csak azt kell megmutatnunk, hogy (3) értéke nem nő. Ehhez pedig elegendő ellenőrizni, hogy az a változás, amit egyetlen ember okoz, nem lehet pozitív, hiszen az összes változás az emberek által okozott változások összege. Legyen az expedíciónak az általunk vizsgált tagja a pontnál. Három dolgot csinálhat: -ben marad, előremegy -be, vagy pedig visszafelé -be. Az első esetben -ben 1 liter vizet megiszik, azaz -t eggyel csökkenti, a változás , negatív. A második esetben liter vizzel a kulacsában -be indul, akkor -t -szel, -t eggyel csökkentette, -et -gyel, -et pedig eggyel növelte. A változás: | |
Végül a harmadik esetben, ha -be liter vízzel indul (és literrel érkezik), akkor a változás | | Ezzel az állítást beláttuk. Második változat Láttuk, hogy 2 napi járóföldre 1 liter vizet 6 literből lehet eljuttatni. Ezt ennél kevesebbel már nem lehet megtenni. Ugyanis az, aki a vizet a célba juttatja, megiszik 4 litert (kettőt oda, kettőt vissza), és 1 litert letesz a sivatagban. Ezt az 5 litert egyetlen ember használja fel, de egyetlen alkalommal legfeljebb 3 litert tud magával vinni. Ezért vagy visszafordul a többi vízért ‐ de akkor 4 napnál tovább tartózkodik a sivatagban, és legalább 5 liter víz jár neki ‐ vagy valaki beviszi a sivatagba a további 2 litert ‐, de ekkor ennek az embernek jár még további 1 liter víz. Nézzük meg mi történik, ha a d) feltétel helyett olyan feltételt teszünk, amely megengedi, hoyg az expedíció tagjai fél nap elteltével is visszaforduljanak : az expedíció tagjai napközben nem állhatnak meg, és visszafordulni is csak fél nap elteltével lehet.
5. ábra A feltétel biztosítja azt is, hogy a nap végére mindenki egész napi járásra legyen a tábortól. Az ebben az esetben is szükséges vízmennyiséget az első megoldásban használtakhoz hasonlóan határozzuk meg. Ennek érdekében tegyük fel, hogy az expedíció sikeresen végrehajtotta a feladatát úgy, hogy a feltétel is teljesült. Jelölje most is a tábortól napi járóföldre levő pontot, és azt a vízmennyiséget, ami -be vagy azon túl eljutott. Legyen azoknak a száma, akik -től -ig mentek (mindenkit annyiszor számítva, ahányszor ezt az utat megtette), pedig azoké, akik től -ből -be mentek (5. ábra). Az első utat persze csak délelőtt, a másodikat csak délután tehették meg. Természetesen -től vissza -be is ember ment, -től -ig pedig . Ez összesen félnapos utat jelent, tehát az expedíció tagjai és között legalább teljes napot töltöttek. Így ezen az útszakaszon legalább liter víz fogyott el. Ezt és a -be eljutott liter vizet -ből el kellett hozni, tehát az alábbi egyenlőtlenségeknek fenn kell állniuk: Másrészt -be összesen ember jutott el, és ezek vitték a liter vizet -be: A (4)‐6) összefüggések és segítségével könnyen tudunk alsó korlátot mondani -re. (6) alapján , (4)-ből , (5)-ből pedig . Ismét (6) szerint , majd (4)-ből és (5)-ből és . Általában (ezt például -re vonatkozó indukcióval igazolhatjuk), ezért . Összefoglalva, a táborban eredetileg legalább liter víz volt. Annak meggondolását, hogy ennyi vízzel a feladat a feltétel betartása mellett végre is hajtható, az olvasóra bízzuk. A 6. ábrán azt mutatjuk be, hogyan lehet liter vízzel három napi járóföldre 1 liter vizet eljuttatni. A körökből induló nyilak az expedíció tagjainak útját jelzik, a szaggatott nyilak pedig azt, hogy ki és hol itta meg a szállított vizet. 6. ábra Harmadik változat Ahhoz, hogy három napi járóföldre egy liter vizet az első változat szerint eljuttassunk, a táborban literre van szükség. Ha a második szerint akarjuk ezt megtenni, liter is elég. Lehet-e ezt a vízmennyiséget még lejjebb szorítani? Bizony lehet: A feladat elvégzéséhez 10 liter is elég: Az expedíció munkáját például a következőképpen szervezhetjük (7. ábra). Az egyik (és feltehető, hogy egyetlen) tag az első nap háromszor fordul, és összesen 9 liter vizet napi járóföldre bevisz a sivatagba, a tizedik litert valamikor napközben a táborban megissza. Az első nap végén 9 liter vízzel a sivatagban éjszakázik, napi járóföldre a tábortól. A második nap ismét háromszor fordul, s második éjszakáját 8 liter víz társaságában a tábortól napi járóföldre tölti. Ebből a nyolc literből egyet itthagy, egyet a harmadik nap folyamán megiszik, s 6 litert ‐ kétszer fordulva ‐ további napi járófölddel beljebb visz. 7. ábra Ezzel a pontot napi járóföld távolságra megközelítette. Negyedik nap a 6 literből kettőt innen további távolságra visz és azt ott leteszi, majd visszamegy a sivatagban hagyott 4 liter vízhez, abból egyet megiszik, a megmaradt 3 literrel éppen -be jut, hiszen . Nézzük, hogy az ötödik nap reggelén mi a helyzet. Emberünk tele kulaccsal egy napi járóföldre van. és között a sivatagban (-tól napi járóföldre) egy liter, és között (-től napi járóföldre) két liter víz van. Minden el van rendezve tehát, bátran nekivághat a célhoz vezető útnak. és között odaúton az egyik, visszaúton a másik liter vizet issza meg, és között kulacsának tartalmára támaszkodhat, végül -ből visszafelé a táborba szintén megtalálja az aznapra szükséges 1 liter vizet. Azt, hogy ennél kevesebb víz nem elegendő, nem bizonyítjuk. Viszont megmutatjuk, hogy legalább liter víznek lennie kell a táborban ahhoz, hogy az expedíció tagjai napi járóföldre be tudjanak vinni 1 liter vizet az a), b'), c) feltételek mellett. A bizonyítás módszeréűl a már bemutatott ,,értékelési eljárást" választjuk. Ha egy nap végén a tábortól napi járóföldre liter víz van, legyen annak értéke ; ha ott az expedíció egy tagja tartózkodna, annak értéke . A fenti állítás azonnal következik abból, hogy estéről estére az összes vízmennyiségnek és az embereknek az értékét összeadva, ez az összeg nem nőhet ‐ ezt pontosan úgy láthatjuk be, mint az első változatban tettük. Azt pedig, hogy az összérték nem nőhet, úgy bizonyítjuk, hogy megmutatjuk: az expedíció bármely tagja által egy nap alatt okozott változás nem pozitív. A teljes változás ugyanis az egyes tagok által okozott változások összege. Nézzük tehát az expedíció egy tagjának egy napi útját. 8. ábra Valamilyen pontból indul, ide-oda ingázik, s végül egy pontba jut el. A megtett út legfeljebb egy napi járóföld. A nap folyamán megiszik összesen 1 liter vizet, s ennek értéke legalább annyi, mintha ezt útjának a táborhoz legközelebbi pontjában () fogyasztaná el. Útja során szállíthatott vizet ‐ természetesen minden pillanatban legfeljebb 3 litert ‐, s ezzel a tevékenységével akkor növeli legjobban a víz összértékét, ha a tábor felé üres kulaccsal megy, a tábortól távolodva pedig maximális mennyiséget visz magával. Feltehetjük még azt is, hogy a pálya nem tartalmaz két, a sivatag felé záródó ,,hurkot" (9. ábra). 9. ábra Vágjuk le ugyanis azt, amelyik a táborhoz közelebb kezdődik, és illesszük a másik végére. Ezzel a megteendő út nem változik, ugyanakkor a hurok eredeti helyén ‐ mondjuk -tól -ig ‐ szállított víz értéke -ról -re nőtt, vagyis a változás , míg a hurok új helyén -től -ig lehet 3 liter vizet szállítani, s a változás , ami miatt több, mint korábban. A 10. ábrán azt mutatjuk be, hogy a hurkok ismételt ,,levágásával" végül is milyen útvonalhoz jutunk: az pontból előremegyünk a pontig, onnan vissza az -ig és -ből előre az végpontig. 10. ábra Jelöljük ezeknek a pontoknak a tábortól mért távolságát (napi járóföldben kifejezve) a megfelelő kisbetűkkel. Az összes megtett út legfeljebb 1, tehát | | (7) |
Az útvonalnak a táborhoz legközelebbi pontja vagy , így az emberünk által napközben elfogyasztott víz értéke legalább . Így a megváltozás legfeljebb
| |
Az első tag azt fejezi ki, hogy emberünk az pontból az -be került; a második azt, hogy -ből 3 liter vizet -ba szállított; a harmadik, hogy szintén 3 litert vitt -ből -be; végül az utolsó tag a nap folyamán elfogyasztott víz értékét becsüli meg. Elegendő tehát megmutatnunk, hogy ez az érték nem lehet pozitív, ha olyan nem-negatív mennyiségek, melyekre a (7) feltételek teljesülnek. Kissé átalakítva, a bizonyítandó egyenlőtlenség: | | (8) | Ha most megengedett értékein belül -et és -et rögzítve -t és -et egymástól távolítjuk, akkor (8) bal oldala nő. Ezt a távolítást csak akkor nem tudjuk megtenni, ha vagy vagy értéke ,,megakad", azaz , vagy valamelyike fennáll. Legyen , akkor (7)-ből , és (8) a következőképpen alakul: A bal oldal ismét akkor veszi fel legnagyobb értékét, ha és ,,távolsága" a legnagyobb, vagyis ha és egyike , a másika . Ezekben az esetekben ez az egyenlőtlenség fennáll. Ha , akkor (7) első egyenlőtlenségéből , a másodikból , tehát . A bizonyítandó egyenlőtlenség | | nyilvánvalóan teljesül. Hasonlóan igazolható (8) abban az esetben is, ha . Ez pedig azt jelenti, hogy állításunkat igazoltuk: a feladat végrehajtásához legalább liter vízre szükség van.
Negyedik változat Láttuk, hogy liter víz mindenképpen szükséges, de az már nem igaz, hogy ennyi elegendő is. Például -re 3 liternél kevesebb nem elég, és . Megmutatjuk viszont, hogy liter már elég, még akkor is, ha azt a többletfeltételt szabjuk, hogy ) az expedíció egyetlen tagja sem ,,ingázhat", azaz mindenki a sivatag egy pontjáig előremegy, ott megfordul, s visszatér a táborba. Definiáljuk az valamint a sorozatokat a következőképpen: ; továbbá -re az a legkisebb egész, amelyre , valamint . Az alábbi táblázatban a két sorozat kezdő tagjait tüntettük fel:
Lássuk, hogyan tudunk a d** feltétel mellett 1 liter vizet n napi járóföldre eljuttatni. Először is indítsunk el an embert tele kulaccsal a sivatagba. Mindannyian nem egészen fél napi járóföldre leteszik a náluk levő 3‐3 liter vizet, s sietve visszafordulnak a táborba, hogy azt még napnyugta előtt elérjék. A táborba visszaérve isszák meg az erre a napra járó 1‐1 liter vizüket. Ezzel majdnem fel napi járóföldre 3an≧2bn-1 liter vizet juttattunk el. Másnap an-1 embert indítunk teli kulaccsal. Dél felé (nem sokkal előtte) elérik az előző nap otthagyott 2bn-1 liter vizet, megisznak belőle összesen an-1 liternyit, majd továbbmennek. Másnap az 1 napi járóföldre levő P1 ponttól valamivel kevesebb, mint 1/4 napi járóföldre mindegyikük leteszi az összes vizét ‐ összesen 3an-1≧2bn-2 litert ‐, majd visszafordulnak, s még napnyugta előtt elérik az elsőként telepített ,,tartályt". Ott megisszák a második napi fejadagjukat. Mivel egy napi járásnál kevesebbre vannak a tábortól, a harmadik napra járó vizet már otthon isszák meg. Ezek után an-2 ember indul útnak. Első nap az első tartályból isznak, második nap a másodikból, s a nap végére elérkeznek P2-be. Harmadnap nem egészen 1/8 napi járófölddel továbbmennek, ott leteszik a náluk levő 3an-2≧2bn-2 liter vizet, s visszafordulnak. Még napnyugta előtt elérik a második tartályt, s a következő nap érkeznek az első tartályhoz, az utolsó napi feladagjukat ők is a táborban kapják meg stb. Miután az az a2=1 darab ember is visszatért a táborba, aki a Pn-2 ponton túl 1/2n-1 napi járóföldre tette le a nála levő 3 liter vizet, a P0 és P1 közti tartályból 2(an-1+an-2+...+a2) liter hiányzik, a P1 és P2 közöttiből 2(an-2+an-3+...+a2 liter, a P2 és P3 közöttiből 2(an-3+an-4+...+a2 stb. de ezekben a tartályokban eredetileg legalább 2bn-1, 2bn-2 stb. liternyi volt, és bi=ai+bi-1+...+a2+1 minden i≧2-re. Ezért mindegyik tartályban még legalább 2 liter víznek kellett maradnia. Az expedícó utolsó tagja tehát most már eljuttathatja az 1 liter vizet Pn-be. Nézzük összesen hány liter vizet használtunk fel. A táborból an+an-1+...+a2+1=bn ember indult útnak. Mindegyikük 3 liter vizet vitt magával, s az utolsót kivéve a táborba való visszatéréskor mindegyikük még egy liter vizet ivott. Ez összesen Mn=4bn-1 liter, ezt az értéket kell megbecsülnünk. Az ai számok választása miatt 3ai+1≦2bi+2, tehát Ezt az összefüggést ismételten alkalmazva kapjuk, hogy | bn≦(53)n-i⋅bi+23(1+53+...+(53)n-i-1)=(53)n-i(bi+1)-1. | Innen i=6 választással kapjuk, hogy n≧6 esetén | Mn≦(53)n⋅4⋅(35)6(b6+1)-5≦3,92⋅(53)n. |
Ha pedig n<6, akkor közvetlenül is ellenőrizhető, hogy Mn≦4⋅(5/3)n.
|