Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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 a tegyük a helyére. Ezt követően az 1-es helyére berakhatjuk azt a korongot, amely a felszabaduló helyre illik. Ezután két lehetőség van: vagy tudjuk folytatni egy következő korong megfelelő helyre helyezésével, vagy nem, ez utóbbi eset akkor következik be, ha a jobb szélső hely szabadult fel. De az mindenképpen igaz, hogy három lépésből a két korongot helyre tudjuk tenni. Tehát az első 2020 korong legfeljebb \(\displaystyle 3\cdot(2020/2)=3030\) lépésből a helyére tehető. Látható az is, hogy pontosan akkor használunk három lépést két korong saját helyére juttatásához, ha ezek egymással voltak megcserélve a kiindulási helyzetben. Ekkor a csere után mindig a jobb szélső hely marad szabadon. Ez viszont azt jelenti, hogy a 2021. korong éppen a helyén van a 2020 és 2019 cseréjekor, tehát a 3030 csere elegendő. Maximális számú cserére van szükség, ha pl. 2, 1, 4, 3, 6, 5, ..., 2020, 2019, 2021 sorrendben vannak a korongok.


Statisztika:

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


A KöMaL 2021. decemberi matematika feladatai