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:
Problems in Mathematics of KöMaL, December 2021