Problem K/C. 712. (December 2021)

K/C. 712. We have 2022 square wooden plates arranged in a row, and 2021 discs numbered 1 to 2021. One disc is placed on each wooden plate except for the last one, in a random order. Then in each move, one disc is transferred to the (momentarily) vacant wooden square. Our goal is to have the numbers in increasing order, with the last square left vacant. What is the maximum number of moves that may be needed to achieve that goal? Also give an example for a possible initial arrangement that does require that maximum number of moves.

(5 pont)

Deadline expired on January 10, 2022.

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

Megoldás. Ha az 1-es korong nincs a helyén, akkor helyezzük először a jobb szélen levő üres négyzetre azt a korongot, amely az 1-es helyén van, majd az 1-est tegyük a helyére. Ezt követően az így felszabadult helyre berakhatjuk azt a korongot, ami oda illik. Ezután két lehetőség van: vagy tudjuk folytatni egy következő korong megfelelő helyre tevésével, vagy nem, ez utóbbi eset akkor következik be, ha a jobb szélső hely szabadult fel és az 1-es érme egy másikkal fel volt cserélve. Az mindenképpen igaz, hogy három lépésből a két korongot a megfelelő helyre tudjuk tenni. Ha még egy lépésre van lehetőségünk, és utána akadunk el, akkor pedig három korongot tettünk helyre négy lépésben, vagyis három korong biztosan a helyére tehető legfeljebb négy lépésben.

Mivel a 2021 páratlan, a legtöbb lépés vagy úgy lesz szükséges, hogy 2020/2 darab korong párban van, egy pedig kívánt sorrend szerinti helyén, ez \(\displaystyle 3\cdot(2020/2)=3030\) lépés; vagy úgy, hogy 2018/2 darab pár van, és három korongot egymás között kell cserélgetni, ez pedig \(\displaystyle 3\cdot(2018/2)+4=3031\) lépés. Ez utóbbi a több, tehát ez a maximális lépésszám.

Ennyi cserére van szükség, ha pl. 2, 1, 4, 3, 6, 5, ..., 2021, 2019, 2020 sorrendben vannak a korongok.

Statistics:

150 students sent a solution.
5 points:	Bacsek Emma Borbála, Balog Benedek, Bérczes Botond, Bettesch Emma Léda, Buday Noémi, Bukor Emőke Zsuzsanna, Fehér Eszter, Fehérvári Donát, Ferencsik Zsombor, Ferenczi Bence, Fodor Dóra, Fodor Gergely, Fórizs Emma, Hajdu Márton, Han Ziying, Haskó Emma, Horváth 221 Zsóka, Inokai Ádám, Kerekes András, Körmöndi Márk, Laskai Botond, Markovics Benjámin, Mező Levente, Nagy 292 Korina, Papp Zsófia, Petrányi Lilla, Somogyi Dóra, Sütő Áron, Tamás Gellért, Téglás Dorka, Töreczki Gábor.
4 points:	Ali Richárd, Böröczky András Bálint, Dukát Levente, Görcsös Ákos Attila, Görömbey Tamás, Iván Máté Domonkos, Koós Andor, Kovács Artúr Mihály, Lajos Luca, Márfai Dóra, Miszori Gergő, Princz-Jakovics Anna, Szeibert Dominik, Szemző Dávid, Tasnády-Szeőcs Zoltán, Tomesz László Gergő, Ujpál Bálint, Végh Lilian.
3 points:	15 students.
2 points:	5 students.
1 point:	27 students.
0 point:	21 students.
Unfair, not evaluated:	22 solutionss.
Not shown because of missing birth date or parental permission:	2 solutions.

Problems in Mathematics of KöMaL, December 2021