A K. 824. feladat (2024. október)

K. 824. Az \(\displaystyle \textrm{ABABABABABAB}\) betűsorból kiindulva minden lépésben felcserélhetünk két szomszédos betűt. Legalább hány lépésre van szükség ahhoz, hogy eljussunk az \(\displaystyle \textrm{AAAAAABBBBBB}\) betűsorhoz?

(5 pont)

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

Megoldás. Az \(\displaystyle \textrm{A}\) betűk helyszámának összege kezdetben \(\displaystyle 1+3+5+7+9 +11 = 36\), a végállapotban \(\displaystyle 1+2+3+4+5+6 = 21\). Minden lépésben vagy 1-gyel nő, vagy 1-gyel csökken valamelyik \(\displaystyle \textrm{A}\) betűnek a helyszáma (egyszerre csak egynek nőhet, illetve egynek csökkenhet). Ezért legalább 15 olyan lépésre szükség van, amelyben az A betűk összes helyszáma csökken (mert egy lépésben maximum 1-gyel tud csökkenni). 15 lépéssel meg is oldható a feladat: mindig \(\displaystyle \textrm{AB}\) cserét kell csinálnunk úgy, hogy az \(\displaystyle \textrm{A}\) betű balra haladjon; csak akkor nem tudunk ilyet csinálni, amikor már előállt a kívánt végállapot.

Statisztika:

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

A KöMaL 2024. októberi matematika feladatai