Az A. 859. feladat (2023. szeptember)

A. 859. Adott egy $\displaystyle n$ csúcsú $\displaystyle U$ útgráf, melynek az egyik csúcsában egy bekötött szemű játékos tartózkodik. Az út csúcsai meg vannak számozva $\displaystyle 1$-től $\displaystyle n$-ig a természetes számokkal, nem feltétlenül a szokásos sorrendben. Egy lépésben a játékvezető elárulja a bekötött szemű játékosnak, hogy $\displaystyle 1$- vagy $\displaystyle 2$-fokú csúcsban van. Ha $\displaystyle 1$-fokú csúcsban van, akkor csak az egyetlen szomszédjába léphet, $\displaystyle 2$-fokú csúcs esetén pedig a játékos eldöntheti, hogy a kisebb vagy nagyobb sorszámú szomszédba szeretne lépni. A játékos összes információja $\displaystyle k$ lépés után a $\displaystyle k$ darab fokszám, amit elárultak neki, és emlékszik a saját választásaira is. Van-e olyan stratégiája a játékosnak, amellyel biztosan meg tudja állapítani véges sok lépésen belül, hogy hány csúcsa van az útnak?

Javasolta: Németh Márton (Budapest)

(7 pont)

A beküldési határidő 2023. október 10-én LEJÁRT.

Van ilyen stratégia.

Azt nevezzük egy algoritmusnak, ami minden lépésben leírja, hogy kisebb vagy nagyobb szomszédba lépjünk, és minden lépésben megjósolja, hogy egy $\displaystyle 1$ fokszámú csúcsba lépünk-e azzal a lépéssel. Azt mondjuk, hogy egy algoritmus hibába ütközik, ha az előírt lépéseket követve úgy lépünk $\displaystyle 1$ fokú csúcsba, hogy az algoritmus nem jósolta arra a lépésre, vagy pedig nem lépünk $\displaystyle 1$ fokú csúcsba egy olyan lépésnél, amiről az algoritmus azt jósolta, hogy abba fogunk lépni.

Lemma: Egy $\displaystyle n$ hosszú út minden sorszámozására létezik olyan véges hosszú alogritmus, ami ebben az útban követhető, de minden $\displaystyle n$-nél hosszabb úton futtatva hibába ütközik.

Ha a lemma igaz, könnyű belátni a feladat állítását. Minden $\displaystyle k$-ra véges sok sorszámozása létezik egy $\displaystyle k$ hosszú útnak, ezek mindegyikének az algoritmusát lefuttatjuk, először $\displaystyle k=1$-re, aztán $\displaystyle k=2$-re, és így tovább. Ha valójában az út $\displaystyle n$ hosszú, akkor a $\displaystyle k<n$ hosszú utakhoz tartozó algoritmusok mind hibába ütköznek, így tudni fogjuk, hogy az út legalább $\displaystyle n$ hosszú. Ezután az $\displaystyle n$ hosszú út összes sorszámozásához is sorban futtatjuk a hozzájuk tartozó algoritmust. Mivel az út valójában $\displaystyle n$ hosszú, a valódi sorszámozásához tartozó algoritmus nem ütközik hibába. Abból, hogy valamelyik algortimus nem ütközött hibába, tudhatjuk, hogy az út nem lehet $\displaystyle n$-nél hosszabb. Tehát ebből kiderül, hogy az út $\displaystyle n$ hosszú. Mivel minden algortimus véges hosszú, és minden $\displaystyle n$-re véges sok algoritmust kell lefuttatni, amíg idáig eljutunk, ezért ez a stratégia véges sok lépésben megállapítja, hány csúcsa van az útnak.

Lemma bizonyítása:

Adott egy $\displaystyle n$-hosszú út sorszámozással együtt, ezt $\displaystyle U$-nak nevezzük. Ehhez készítünk algoritmust. Először feltesszük, hogy kezdetben az $\displaystyle 1$-es számú csúcsában állunk. Elvégezzük azt a lépéssorozatot, ami az $\displaystyle U$ útban az $\displaystyle 1$-es csúcsból elvinne az egyik végpontba. Ha ennek a végén nem egy végpontban vagyunk, vagy már korábban egy végpontba léptünk, az azt jelenti, hogy nem az $\displaystyle 1$-es csúcsból indultunk. Ekkor feltesszük, hogy a $\displaystyle 2$-es csúcsból indultunk eredetileg. Ha az eddigi lépéssor eredménye nem konzisztens azzal, hogy a $\displaystyle 2$-esből indultunk, akkor ezt is elvetjük, és feltesszük, hogy a $\displaystyle 3$-asból indultunk. Ha konzisztens, akkor megnézzük, hova értünk volna el az $\displaystyle U$ útban a $\displaystyle 2$-esből indulva az eddigi lépéssorozattal, majd elvégezzük azt a lépéssorozatot, ami onnan elvinne az egyik végpontba $\displaystyle U$-ban. Ha ez is hibába ütközik, akkor feltesszük, hogy eredetileg a $\displaystyle 3$-as csúcsból indultunk... és így tovább, amikor hiba van, feltesszük, hogy eggyel magasabb sorszámú csúcsból indultunk, egészen az $\displaystyle n$-es sorszámig. Ez egy véges hosszú algoritmus (legfeljebb $\displaystyle n^2$ lépésből áll), és ha valóban az $\displaystyle U$ útban vagyunk, akkor bárhonnan indultunk, ez az algoritmus idővel elvisz egy végpontba.

Az eddigi bolyongást el is felejtjük, és ezután csak az a célunk, hogy készítsünk egy véges hosszú algoritmust, ami egy végpontból indul, és $\displaystyle U$-ban futtatható, de minden $\displaystyle n$-nél hosszabb úton hibához vezet.

Az általánosság rovása nélkül mondhatjuk, hogy a bal végpontból indultunk. Az első menetben kilépünk a végpontból, ekkor biztosan balról a második csúcsban állunk.

$\displaystyle k\le\frac{n+1}{2}$-re a $\displaystyle k$-adik menet elején tudjuk, hogy balról a $\displaystyle k$-adik csúcsban állunk. Ezután elvégezzük azt a lépéssorozatot, ami $\displaystyle U$-ban balról a $\displaystyle k$-adik csúcsból bevinne a bal végpontba, és az algoritmus azt jósolja, hogy ekkor egy $\displaystyle 1$ fokú csúcsban vagyunk. $\displaystyle U$-ban ez működik, egy $\displaystyle n$-nél hosszabb útban pedig ez vagy hibához vezet, vagy ha nem, az csak úgy lehetséges, ha egyenesen visszamentünk a bal végpontba, ugyanis $\displaystyle k\le \frac{n+1}{2}$ miatt a balról a $\displaystyle k$-adik csúcsból nem juthattunk el $\displaystyle k-1$ lépésben a jobb végpontba, továbbá az útnak egyenesnek kellett lennie, különben $\displaystyle k-1$ lépés nem lett volna elég eljutni a bal végpontba se a $\displaystyle k$-adik csúcsból. Ekkor elvégezzük azt a lépéssorozatot, ami az előző menetben elvitt a bal végpontból a $\displaystyle k$-adik csúcsba. Ez most is biztosan odavisz. Majd megnézzük, hogy a mostani menet elején a $\displaystyle k$-adik csúcsból a kisebb vagy nagyobb szomszédba léptünk. Tudjuk, hogy ez vezet a bal végpont irányába, így most az ellenkező irányba lépünk. Így biztosan a balról $\displaystyle k+1$-edik csúcsban állunk a menet végén.

Ezt iteráljuk amíg $\displaystyle k\le \frac{n+1}{2}$.

Ha $\displaystyle n$ páros, akkor tudjuk, hogy ezzel végül a balról $\displaystyle \frac{n}{2}+1$-edik csúcsba érkezünk, ha $\displaystyle n$ páratlan, akkor a balról $\displaystyle \frac{n+3}{2}$-ik csúcsba. Ekkor elvégezzük azt a lépéssorozatot, ami $\displaystyle U$-ban elvinne innen a jobb végpontba. Az algoritmus azt jósolja, hogy ezzel egy $\displaystyle 1$ fokszámú csúcsba érünk. Az $\displaystyle U$ úton ez teljesül, egy $\displaystyle n$-nél hosszabb úton viszont ez túl kevés lépés ahhoz, hogy bármelyik végpontba elérjünk vele, így biztosan hibába ütközünk.

Összességében tehát ez egy olyan véges algoritmus, ami az $\displaystyle U$ úton jól fut, de minden hosszabb úton hibába ütközik.

Statisztika:

19 dolgozat érkezett.
7 pontot kapott:	Czanik Pál, Duchon Márton, Tarján Bernát, Varga Boldizsár, Wiener Anna.
6 pontot kapott:	Farkas 005 Bendegúz, Holló Martin, Vigh 279 Zalán.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2023. szeptemberi matematika feladatai