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:

38 dolgozat érkezett.
6 pontot kapott:	Ali Richárd, Bánhegyi Botond, Bencze Mátyás, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Diaconescu Tashi, Görömbey Tamás, Gyenes Károly, Hajba Milán, Holló Martin, Horák Zsófia, Kovács Benedek Noel, Kővágó Edit Gréta, Molnár István Ádám, Pletikoszity Martin, Prohászka Bulcsú, Sánta Gergely Péter, Sha Jingyuan, Szabó 721 Sámuel, Tamás Gellért, Vámosi Bendegúz Péter, Vigh 279 Zalán, Virág Lénárd Dániel, Vödrös Dániel László.
5 pontot kapott:	Aravin Peter.
4 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	3 versenyző.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2024. októberi matematika feladatai