Ha a történelemben a 300 a spártaiak kitartásának szimbóluma, akkor itt, az Ész Ventura rovatban a ti szellemi állóképességeteké. Ez a jubileum ugyanis nemcsak a rovatról szól, hanem arról a kíváncsi és elszánt közösségről is, amely hétről hétre velünk tart. Nincs is jobb módja az ünneplésnek, mint az, hogy vegyetek elő papírt, ceruzát és természetesen a legélesebb logikátokat, hogy ne fogjon ki rajtatok a 300. Ész Ventura-feladvány se!

300. feladvány: Vírusvadászat

Újabban egy agyafúrt vírus fertőzi a céges rendszereket, és céges adatokat próbál szerezni. Ha a vírus bejut egy céges hálózatba, akkor akkor megpróbál egyetlen gépen elbújni, éjfélkor azonban mindig átugrik egy szomszédos gépre, vagyis átmásolja magát, a régi helyről pedig törlődik. Ez a stratégia azért kiváló számára, mert a normál vírusvédelmi szoftvereknek nem elég egy nap, hogy felfedezzék. A rendszergazda képes ugyan komolyabb nyomozást folytatni egy gépen, de az egy napot és sok erőforrást igényel, ezért naponta legfeljebb két gépen tud olyan keresést futtatni, ami rátalál a vírusra, persze csak akkor, ha a vírus éppen azon a gépen tartózkodik. Ha viszont a vírus nem azon a gépen tartózkodik, sajnos csak ennyit tudunk meg, mert a vírus nem hagy maga után nyomot a gépeken.

Ha a céges hálózat alakja a fent látható fektetett 8-as, vagyis két körből áll, amik egy pontban csatlakoznak egymáshoz, akkor vajon a rendszergazda meg tudja-e biztosan találni a vírust véges időn belül a napi két darab célzott keresési lehetőség kihasználásával?

Ha a gépek egy vonal mentén kapcsolódnának, vajon napi egy keresés is elég lenne?

Nézzünk előbb egy olyan problémát, amikor véges sok gép sorba van kötve egymással, ahogy az alábbi ábrán is látszódik, viszont naponta csak egy gépet tud átnézni a rendszergazda.

Képzeljük úgy, hogy a gépek felváltva pirosra és kékre vannak színezve. Mivel a vírus minden éjjel átköltözik egy szomszédos gépre, ez azt jelenti, hogy minden egyes lépésnél színt vált. Ha ma piros gépen tartózkodik, akkor holnap biztosan kéken lesz, és fordítva. Mivel nem tudjuk, hol kezdett a vírus, két lehetőség van, vagy minden páratlan napon piros gépen tartózkodik, és minden pároson kéken, vagy fordítva.

Tegyünk egy próbát, és keressük úgy, mintha biztosan tudnánk, hogy a vírus piros gépről kezdett. Ezzel a feltételezéssel megpróbáljuk balról indulva beszorítani a vírust. Első nap megnézzük az első bal oldali piros gépet, ha nem találjuk, akkor tudjuk hogy valamelyik másik piros gépen van, és másnapra átlép egy kékre, tehát tőlünk jobbra lesz. Másnap keressük az előző gép jobb oldali kék szomszédján. Ha nem találjuk, akkor tudjuk hogy továbbra is jobbra lesz tőlünk, és így tovább, egyesével haladhatunk jobbra, és közben folyamatosan szorítjuk jobbra a lehetőségeket. Ilyen módon a végén mindenképpen megtaláljuk véges sok lépésen belül, feltéve, hogy pirosról kezdett.

Abban az esetben, ha végigmegyünk a vonalon, és nem találjuk meg, akkor tudjuk, hogy nem pirosról kezdett, hanem kékről. Ekkor viszont ki tudjuk számolni, hogy most éppen milyen színen tartózkodik, és ugyanezt végigcsinálhatjuk ezzel a feltételezéssel újra.

Ha viszont egy vonalon meg tudjuk találni úgy, hogy naponta egy gépen keressük, akkor a 8-as elrendezés esetén is meg tudjuk találni akkor, ha két gépen is kereshetjük naponta. Hiszen megtehetjük azt, hogy a 8-as középpontját minden nap megnézzük, így ott a vírus nem tud áthaladni, így viszont két különálló szakaszra esik szét a hálózat, amiket szisztematikusan végig tudunk nézni a fenti módszerrel, előbb az egyiket, és ha ott nem találtuk a vírust, akkor a másikat.

Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, ezt a Vendégkönyvben kifejezésre juttathatod.

Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.

Forrás