Ész Ventura: És azt ismered, hogy Hófehérke fogócskázik a hét törpével?

179. feladványunkban Hófehérke és a hét törpe fogócskázott egy körvonalon. Ebben a játékban Hófehérke a fogó, és akit elkap, annak mozdulatlanul kell maradnia egészen addig, amíg egy másik törpe meg nem érinti. A játékosokról feltételezzük, hogy pontszerűek. A kérdés az volt: ha minden törpe ugyanolyan gyors, Hófehérke pedig egy nagyon picit gyorsabb a törpéknél, akkor meg tudja-e fogni Hófehérke véges idő alatt az összes törpét, vagy tudnak úgy mozogni a törpék, hogy mindig legyen valaki, aki szabadon mozoghat?

Ennél a feladatnál nagyon valószínűnek tűnhet, hogy a sok törpe ki tudja cselezni Hófehérkét, és csábító is azon gondolkodni, hogy a törpék milyen furmányos stratégiával tudnák kicselezni, csakhogy ez nem lehetséges. Ha sok hiábavaló próbálkozás után már sejtjük, hogy nem a törpéknek, hanem Hófehérkének kellene stratégiát találnunk, akkor viszont már nem nehéz a feladvány, mert kiderül, hogy Hófehérkének semmi mást nem kell tennie, mint egy irányba futnia végig, és ez garantálja, hogy minden törpét elkap.

Dömők Dávid megoldónk megoldása szépen szemlélteti, hogy ez miért működőképes stratégia Hófehérkének. Tegyük fel, hogy Hófehérkével egy időben, és ugyanabba az irányba elindul egy virtuális törpe is (lásd a halványabb törpét az ábrán) olyan sebességgel, mint a többi törpe maximális sebessége.

photo_camera Illusztráció: Qubit

Ekkor a virtuális törpe le fog maradni Hófehérkéhez képest, de a virtuális törpe előtt és Hófehérke mögött nem lehet mozgó törpe, csak szoborrá változott törpe, hiszen a virtuális törpöt nem tudja másik törpe megelőzni. Mozgó törpe tehát csak Hófehérke előtt és a virtuális törpe mögött lehet, de ezeket Hófehérke előbb-utóbb utol fogja érni, akármilyen kicsivel is fut gyorsabban Hófehérke, ráadásul a törpék száma sem lényeges. Tehát a törpék a számuktól függetlenül veszíteni fognak ebben a játékban, ha Hófehérke rendületlenül fut az egyik irányba.

Másik megoldónk kicsit más szemszögből magyarázza a feladványt. Tegyük fel, hogy Hófehérkéhez rögzítjük a forgó koordinátarendszerünket. Ebben a rendszerben Hófehérke tehát áll, a törpék pedig úgy mozognak, mintha egy kör alakú futószalag folyamatosan szállítaná felé a törpéket. Ha valamelyik törpe nem elfelé fut a lehető legnagyobb sebességgel, akkor ő ebben a rendszerben nem áll a futószalagon, hanem a futószalagon gyalogol Hófehérke felé. Ha Hófehérke megfog egy törpét, akkor azt maga mögé helyezi a futószalag másik végére. Ha egy ilyen törpöt egy másik törpe feléleszt, ettől még egyikük se tud a futószalagon visszafele haladni, ezért együtt közelednek a végzetük felé.