Problem K. 824. (October 2024)

K. 824. Starting from the string of letters ABABABABABAB, in each step we can swap two adjacent letters. Find the minimum number of steps needed to obtain the string of letters AAAAAABBBBBB.

(5 pont)

Deadline expired on November 11, 2024.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

166 students sent a solution.
5 points:	Cseres-Gergely Kinga, Lovas Márk, Maróti Dóra Anna, Molnár Levente, Pászti Sámuel, Péter Tamás, Rózsa Péter, Szegedi András.
4 points:	Bálint Barnabás, Barta Zsófia, Bloemsma Péter Sándor, Bodor Benedek, Chen Kewei, Csík Zoltán Richárd, Győrffy Csanád, Harangozó Bálint, Holló Barnabás, Kudomrák Lili Anna , Kun Milán, Lay Kristóf, Medgyesi András, Osztényi Áron , Patócs 420 Péter, Szighardt Anna, Sztankov Áron Attila, Verebély Dániel.
3 points:	14 students.
2 points:	34 students.
1 point:	55 students.
0 point:	17 students.
Not shown because of missing birth date or parental permission:	20 solutions.

Problems in Mathematics of KöMaL, October 2024