Problem B. 5412. (October 2024)

B. 5412. A fugitive at a vertex of a finite connected graph is being chased by three policemen at three other vertices. First the fugitive makes a move along an edge, then each of the three policemen can also make a move along an edge. The game continues by alternating turns between the fugitive and the policemen. Can the policemen always catch the fugitive in a finite number of steps, i.e., can they always guarantee that one of them will be on the same vertex as the fugitive after a finite number of steps?

Proposed by Péter Pál Pach, Budapest

(6 pont)

Deadline expired on November 11, 2024.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

38 students sent a solution.
6 points:	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 points:	Aravin Peter.
4 points:	1 student.
3 points:	1 student.
1 point:	7 students.
0 point:	3 students.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, October 2024