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