A B. 5412. feladat (2024. október)

B. 5412. Egy összefüggő véges gráf egyik csúcsában van egy szökevény, akit a gráf három másik csúcsában lévő rendőrök szeretnének elkapni. Először a szökevény lép egyet egy él mentén, majd a rendőrök is léphetnek egyet-egyet, szintén élek mentén. Ezután ezt így folytatják felváltva. Biztosan el tudják-e kapni a rendőrök a szökevényt, vagyis garantálni tudják-e, hogy valamelyikük véges sok lépésen belül a szökevénnyel egy csúcsra kerüljön?

Javasolta: Pach Péter Pál (Budapest)

(6 pont)

A beküldési határidő 2024. november 11-én LEJÁRT.

Megoldás. Azt fogjuk belátni, hogy nem biztos, hogy el tudják kapni, megadunk egy gráfot, aminél a szökevény el tudja érni, hogy ne kapják el.

Legyen a gráf csúcshalmaza a 7 hosszú \(\displaystyle 0-1\)-sorozatok halmaza, két csúcs pedig pontosan akkor legyen éllel összekötve, ha pontosan egy helyen különböznek, tehát például a \(\displaystyle (0,0,0,0,0,0,0)\) csúcs szomszédjai a pontosan egy darab 1-est tartalmazó sorozatok. (Másképpen, a gráfot a 7-dimenziós hiperkocka csúcsai és élei alkotják.) A gráf minden csúcsából 7 él indul, két csúcs távolsága pedig annyi, ahány helyen a két sorozat eltér.

A szökevénynek arra kell figyelnie, hogy lépése után mindhárom rendőrtől legalább 2 távolságra legyen. Ha ezt mindig garantálni tudja, akkor nem kapják el (különben pedig igen). Tekintsünk egy olyan pillanatot, amikor a szökevény lép. Mivel eddig nem kapták el, minden rendőr legalább 1 távolságra van tőle. Ha egy rendőr legalább 3 távolságra van, akkor a szökevény lépésétől függetlenül megmarad a legalább 2-es távolság. Ha egy rendőr 2 távolságra van, akkor van 2 lépés, aminél 1-re csökkenne a távolság (ha az egyik eltérő helyen vált a sorozatában értéket), a másik 5-nél 3-ra nő. Ha egy rendőr 1 távolságra van, akkor van 1 lépés, aminél a szökevény odamenne a rendőrhöz, a másik 6-nál 2-re nő a távolság. Tehát mindegyik rendőrnél legfeljebb 2-féle rossz irány van, így a 7-féle lehetséges lépés közül \(\displaystyle 7-2\cdot 3=1>0\) miatt mindenképpen tud megfelelőt választani a szökevény.

Ezzel a bizonyítást befejeztük.

Statisztika:

A B. 5412. feladat értékelése még nem fejeződött be.

A KöMaL 2024. októberi matematika feladatai