A K/C. 712. feladat (2021. december)

K/C. 712. Egymás mellé helyezünk 2022 db négyzet alakú falapot, majd 2021 db korongra felírjuk az egész számokat 1-től 2021-ig. A korongokat tetszőleges sorrendben elhelyezzük a falapokon úgy, hogy a jobb szélső négyzetre nem helyezünk korongot (minden falapra egy korong kerül). Ezek után egy lépésben egy tetszőleges korongot áthelyezhetünk az éppen üresen álló fanégyzetre. A célunk az, hogy a korongokon álló számok balról jobbra haladva növekvő sorrendben legyenek, és a jobb szélső négyzet üres legyen. Maximálisan hány lépésre van ehhez szükségünk? Mutassunk is olyan kezdeti elrendezést, amely az általunk megállapított maximális lépésszámot igényli a sorba rendezéshez.

(5 pont)

A beküldési határidő 2022. január 10-én LEJÁRT.

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.

Statisztika:

150 dolgozat érkezett.
5 pontot kapott:	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 pontot kapott:	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 pontot kapott:	15 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	27 versenyző.
0 pontot kapott:	21 versenyző.
Nem versenyszerű:	22 dolgozat.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	2 dolgozat.

A KöMaL 2021. decemberi matematika feladatai