Az A. 914. feladat (2025. október)

A. 914. A táblára felírjuk az \(\displaystyle (1,0)\) rendezett számpárt. Egy lépésben, ha a táblán az \(\displaystyle (a,b)\) számpár áll, akkor letöröljük, és felírjuk helyette vagy az \(\displaystyle (a+b,b)\), vagy pedig a \(\displaystyle (2a+b,a+b)\) számpárt. (Például két lépés után az \(\displaystyle (1,0)\), \(\displaystyle (2,1)\), \(\displaystyle (3,1)\) és \(\displaystyle (5,3)\) párok valamelyike állhat a táblán.) Mutassuk meg, hogy \(\displaystyle n\) lépés után a táblán lévő rendezett számpár pontosan \(\displaystyle 2^n\)-féle lehet.

Javasolta: Imolay András (Budapest)

(7 pont)

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

Vezessük be az \(\displaystyle (a,b)\rightarrow(a,a+b)\) lépést, és vegyük észre, hogy az \(\displaystyle (2a+b,a+b)\) számpár megkapható úgy, hogy \(\displaystyle (a,b)\)-re először az előbb definiált lépést, majd a feladatban eredetileg szereplő \(\displaystyle (x,y)\rightarrow (x+y,y)\) lépést alkalmazzuk. Így a feladat a következő módon fogalmazható át: az \(\displaystyle (a,b)\rightarrow(a+b,b)\) lépéseket és az \(\displaystyle (a,b)\rightarrow (a,a+b)\) lépéseket alkalmazzuk az \(\displaystyle (1,0)\)-ból kiindulva valamilyen sorrendben, az első típusút pontosan \(\displaystyle n\)-szer, a második típusút valahányszor, de azzal a megkötéssel, hogy ha alkalmazzuk, akkor közvetlenül utána az első típusút kell végrehajtanunk.

Most vegyük észre, hogy az első típusú lépés után mindig a számpár első tagja a nagyobb, a második típusú lépés után viszont mindig a számpár második tagja a nagyobb. Így az eredmény ismeretében mindig tudjuk, hogy melyiket hajtottuk végre utoljára a kétféle lépés közül. Az tehát a kérdés, hogy egy adott számpárból visszafelé haladva meg lehet-e kapni kétféle módon az \(\displaystyle (1,0)\) számpárt. Látszólag maradt még egy lehetőség, hiszen az \(\displaystyle (1,0)\)-ból is tudunk visszafele lépni az \(\displaystyle (1,0)\)-ra az első típusú lépéssel: de mivel kötött, hogy hányat lépünk az első típusú lépésből, ezért egyértelmű, hogy hányszor léphettünk még visszafele az \(\displaystyle (1,0)\)-ból, azaz hogy melyik lépéssorozattal kaptuk meg az \(\displaystyle (1,0)\)-t. Ezzel az állítást beláttuk.

Statisztika:

41 dolgozat érkezett.
7 pontot kapott:	Ali Richárd, Aravin Peter, Bodor Mátyás, Bolla Donát Andor, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Diaconescu Tashi, Ethan Y.Wang, Forrai Boldizsár, Gyenes Károly, Győrfi Ádám, Holló Martin, Horák Zsófia, Kámán-Gausz Péter, Kocsis 827 Péter, Kozma Sándor, Li Mingdao, Liu Zhe, Mihály Zsolt, Morvai Várkony Albert, Nagypál Katóca, Pázmándi József Áron, Prohászka Bulcsú, Rajtik Sándor Barnabás, Rem Dóra, Sánta Gergely Péter, Sárdinecz Dóra, Szabó 721 Sámuel, Szakács Ábel, Tianyue DAI, Varga 511 Vivien, Vigh 279 Zalán, Vödrös Dániel László, Wágner Márton, Xiaoyi Mo.
5 pontot kapott:	2 versenyző.
1 pontot kapott:	2 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2025. októberi matematika feladatai