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:

Az A. 914. feladat értékelése még nem fejeződött be.

A KöMaL 2025. októberi matematika feladatai