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. Kovács Benedek megoldása. A feladat állítása nem igaz: belátjuk, hogy a vadász akármilyen stratégiája esetén a nyomkövető jelezheti pontok olyan sorozatát, hogy a nyúlnak létezzen olyan, a szabályok szerinti lehetséges mozgássorozata, amire . Vagyis ha a nyúl maga jelölheti ki a nyomkövető jelzéseit a számára legkedvezőbb módon, akkor a vadász nem tudja garantálni, hogy -on belül kerüljön a nyúlhoz. Legyen . A nyúl célja az, hogy legyen. Nyilván az is elég számára, ha valamilyen -re , hiszen ha ekkor a nyúl a további lépésekben már mindig a vadásszal ellentétes irányban lép, akkor lépésével a vadásztól való távolságát 1-gyel növeli, a vadász pedig a saját lépésében legfeljebb 1-gyel csökkentheti, vagyis egy fordulón belül a távolság nem csökken, így a -edik forduló után is 100-nál nagyobb lesz.
Lemma. Ha az . fordulóban , a vadász nem tudja garantálni, hogy legyen.
Bizonyítás. A nyúl tehát 200 forduló alatt szeretné a vadásztól vett távolságának négyzetét -nél többel megnövelni. A vadásznak az -edik forduló kezdetekor a nyúl mozgásáról rendelkezésére álló információt a pontok jelentik. Ezen pontok alapján a nyúlnak akár több lehetséges helye is lehet, de most tegyük fel még azt is, hogy a nyúl konkrétan elárulja a helyzetét, az pontot. A korábbi információk így feleslegessé válnak. Jelöljük -lel az egyenest ( esetén tetszőleges egyenest -n keresztül). Mérjük fel az ábra szerint az egyenesre az pontból, -vel ellentétes irányban egységet, így kapva a pontot. A pontban merőlegest állítva -re, ezen a merőlegesen vegyük fel a és pontokat -től 1 távolságra. Ekkor a Pitagorasz-tétel miatt lesz.
A nyúl számára a következő 200 fordulóban az lesz a stratégia, hogy egyenesen elmegy a célpontba (ezt megteheti, hiszen ). Mivel a teljes szakasz 1 távolságon belül van az egyenestől, a nyúl minden fordulóban kijelölheti helyzetének az -re vett merőleges vetületét, mint a nyomkövető által adandó jelzést. Természetesen ugyanezeket a jelzéseket megadhatná a nyúl akkor is, ha nem a , hanem a pontba menne el hasonló módon, hiszen a két útvonal -re nézve szimmetrikus. A vadász így a 200 forduló alatt kapott jelzésekből nem fogja tudni, hogy a vagy a pont felé tart-e a nyúl. Nézzük azt a pontot, ahova a vadász ezalatt eljutott. Ez a pont biztosan a középpontú, 200 sugarú körön belül van, legyen ennek az -lel való (a nyúl irányába eső) metszéspontja . Osszuk fel ezt a kört két részre az egyenes ( felezőmerőlegese) mentén. Az egyik (az ábra szerint felső) részben lévő pontok a célponthoz, a másik (alsó) részben lévők -höz vannak közelebb. A felső rész összes pontjára igaz, hogy legalább olyan távol vannak -től, mint , mert mind vízszintesen, mind függőlegesen legalább olyan távol vannak tőle (ha az ábra szerint, vagyis az egyenessel párhuzamosnak vesszük a vízszintes irányt). Ugyanígy az alsó rész összes pontja legalább olyan távol van -től, mint . Így a két lehetséges célpont közül a távolabbi mindenképpen legalább olyan messze lesz a vadásztól, mint az távolság. Számítsuk ki ezt a távolságot. , így . Így , és a Pitagorasz-tétel alapján | |
Azt kell belátnunk, hogy ez a távolság nagyobb, mint :
Mivel , azaz , elég belátni, hogy
Négyzetre emelve: Ez pedig igaz, mert | |
Ekvivalens lépésekkel dolgoztunk, így a vadász számára rosszabbik távolság legalább , így a lemmát beláttuk.
A lemmából már következik a bizonyítandó állítás: a játék elején , és a lemma szerint (teljes indukcióval) a vadász számára legrosszabb esetben , amíg a távolság el nem éri a -at. Ez az elérés pedig legkésőbb -re bekövetkezik, azaz fordulón belül. Vagyis , azaz . A nyúl ezzel elérte a célját, hiszen . |