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