A B. 4403. feladat (2011. december)

B. 4403. A 20×20-as sakktábla néhány mezőjén bábu áll. Egy bábut akkor vehetünk le a tábláról, ha annak sorában vagy oszlopában a mezőknek legalább a fele üres. Legfeljebb hány bábu lehet a táblán, ha ilyen lépések sorozatával az összeset le tudjuk venni?

(5 pont)

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

Megoldás. Ha 300 bábut úgy helyezünk el a táblán, hogy a jobb fölső \(\displaystyle 10 \times 10\)-es sarok marad üresen, akkor az összeset levehetjük a következő módon. A fölső 10 sorban álló bábuk sorában csak 10 bábu áll, így ezek a bábuk levehetők. Ezután már minden oszlopban csak 10 bábu lesz, így azok is levehetők lesznek. A továbbiakban megmutatjuk, hogy akárhogy is helyezkedik el 300-nál több bábu a táblán, nem lehet az összeset levenni.

Ehhez tekintsük a következő, általánosabb feladatot. Legyenek \(\displaystyle u,v\) pozitív egész számok, és tegyük fel, hogy az \(\displaystyle (n+u)\times (n+v)\)-es sakktábla mezőin helyeztünk el néhány bábut; hívjuk ezt egy \(\displaystyle (u,v)\)-elrendezésnek. Egy bábut akkor vehetünk le a tábláról, ha annak sorában vagy oszlopában legfeljebb \(\displaystyle n\) bábu áll. Az elrendezés levehető, ha ilyen lépések sorozatával az összes bábut le tudjuk venni. Nyilván egy levehető elrendézes összes rész-elrendezése is levehető. Az \(\displaystyle u+v\) mennyiségre vonatkozó teljes indukcióval belátjuk, hogy ha egy \(\displaystyle (u,v)\)-elrendezésben a bábuk száma nagyobb, mint \(\displaystyle n^2+nu+nv\), akkor az elrendezés nem levehető. Ez az \(\displaystyle u=v=10\) esetben feladatunk megoldását szolgáltatja.

Az \(\displaystyle u+v=2\) esetben, vagyis ha \(\displaystyle u=v=1\), az állítás nyilvánvaló: ekkor az \(\displaystyle (n+1)\times (n+1)\)-es tábla minden mezője foglalt, egyetlen bábut sem lehet levenni. Tegyük fel, hogy \(\displaystyle u+v>2\), és van egy olyan levehető \(\displaystyle (u,v)\)-elrendezés, amelyben több, mint \(\displaystyle n^2+nu+nv\) bábu szerepel. Ahhoz, hogy az első bábut levehessük, kell legyen egy olyan sor, vagy oszlop, amelyben legfeljebb \(\displaystyle n\) bábu áll. Mivel a tábla kevesebb, mint \(\displaystyle uv\) mezőjéről hiányzik bábu, az ilyen sorok és oszlopok száma legfeljebb \(\displaystyle u-1\), illetve \(\displaystyle v-1\). Tekintsünk tehát egy olyan sort, vagy oszlopot, amelyben legfeljebb \(\displaystyle n\) bábu áll, és vegyük le az abban álló összes bábut. Ha ily módon egy sort vettünk le, akkor \(\displaystyle u\ge 2\) kellett legyen, és ezzel egy olyan levehető \(\displaystyle (u-1,v)\)-elrendezést kaptunk, amelyben több, mint \(\displaystyle n^2+n(u-1)+nv\) bábu áll. Ha pedig egy oszlopot ürítettünk ki, akkor \(\displaystyle v\ge 2\) kellett legyen, és ezzel egy olyan levehető \(\displaystyle (u,v-1)\)-elrendezést kaptunk, amelyben több, mint \(\displaystyle n^2+nu+n(v-1)\) bábu áll. Bármelyik lehetőség ellentmond az indukciós feltevésnek.

Statisztika:

91 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Havasi 0 Márton, Kabos Eszter, Kecskés Boglárka, Kulcsár Ildikó, Kúsz Ágnes, Maga Balázs, Mester Márton, Mócsy Miklós, Ódor Gergely, Papp Roland, Simon 047 Péter, Szabó 789 Barnabás, Tardos Jakab, Viharos Andor.
4 pontot kapott:	Ágoston Tamás, Bogáromi Dávid, Csernák Tamás, Gyarmati Máté, Nagy Róbert, Paulovics Zoltán, Szabó 524 Tímea, Varnyú József.
3 pontot kapott:	19 versenyző.
2 pontot kapott:	7 versenyző.
1 pontot kapott:	30 versenyző.
0 pontot kapott:	10 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2011. decemberi matematika feladatai