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 feladatot nyilván úgy is lehet értelmezni, hogy ha mi előre kijelöljük a megmérgezendő pontokat, akkor a bolha az irányait meg tudja-e úgy választani, hogy mérgezett pontra ne lépjen. Megmutatjuk, hogy ezt mindig meg tudja tenni.
1. ábra Legyen azoknak az rácspontoknak a halmaza, amelyekre (1. ábra). A bolha nyilván az -edik lépésben ugrik az darab -beli pont valamelyikére. Legyen azoknak az -beli pontoknak a száma, amelyeket legkésőbb az -edik lépésben (tehát a bolha "megérkezéséig'') megmérgezünk. Mivel az első lépésben pontot mérgezünk meg, nyilván .
2. ábra Végül jelölje azoknak az -beli pontoknak a számát, ahová a bolha eljuthat. Ez nem feltétlenül azonos a meg nem mérgezett pontok számával, lehet, hogy egy pontba pl. azért nem juthat el, mert annak megmérgeztük a bal oldali és az alsó szomszédját (2. ábra). Azt fogjuk megmutatni, hogy Mivel , ebből következik, vagyis az -edik lépésben még nem lehetünk biztosak afelől, hogy a bolhát elpusztítottuk (és ez minden -re igaz).
Állításunkat teljes indukcióval igazoljuk; -re igaz: ha , akkor mind a két -beli pontra ugorhat a bolha; ha , akkor pedig az egyikre ugorhat.
Mindkét esetben .
Tegyük most fel, hogy . Megmutatjuk, hogy ekkor .
3. ábra A bolha darab -beli pontra ugorhat; ezeknek összesen legalább jobb oldali vagy felső szomszédja van, mert jobb oldali szomszédaik, valamint a legfelső pont felső szomszédja (ez összesen pont) különbözők (3. ábra). A szóba jövő darab -beli pont közül legfeljebb a mérgezett; a bolha tehát legalább helyre ugorhat tovább úgy, hogy nem lép mérgezett pontra.
Ezzel azt kaptuk, hogy | |
Ezzel az állításunkat igazoltuk; semmilyen -re nem tudjuk garantálni, hogy a bolhát legfeljebb lépésben elpusztíthatjuk.
Megjegyzés. Ha az volna a kérdés, hogy el tudjuk-e pusztítani a bolhát véges sok lépésben, akkor arra is tagadó lenne a válasz. (A különbség lényeges: ha pl. valaki gondol egy pozitív egész számot, azt ki lehet találni véges sok lépésben úgy, hogy végig kérdezzük az összes számot; azt azonban semmiképpen sem tudjuk vállalni, hogy pl. legfeljebb 100 találgatással kitaláljuk.)
Nevezzünk egy rácspontot "jó''-nak, ha a bolha arra lépve még akármilyen sokáig életben tud maradni. A feladat megoldásából az derült ki, hogy az origó "jó'' rácspont.
Bebizonyítjuk, hogy, "jó'' rácspontról a bolha tovább tud ugrani egy újabb "jó'' rácspontra.
4. ábra Legyen egy " jó'' rácspont, a jobb és felső szomszédai legyenek és ( 4. ábra). Tegyük fel, hogy és egyike sem " jó''. Ekkor léteznek olyan és pozitív egészek, hogy a bolha -ra lépve legfeljebb az -edik, -re lépve pedig legfeljebb a -adik lépésben elpusztul. Ekkor viszont a bolha -re lépve legfeljebb a max -adik lépésben (akár -ra, akár -re lép tovább) mindenképpen elpusztul, vagyis sem lehet " jó'' rácspont.
Ezután már nem nehéz a bolha túlélési stratégiáját megadni: ugorjon mindig "jó'' rácspontra. |
|