Problem B. 4403. (December 2011)

B. 4403. There are chessmen standing on some fields of a 20×20 chessboard. The rule is that a chessman can be removed from the board if at least a half of the fields is vacant in its row or in its column. What is the maximum possible number of chessmen on the board if all of them can be removed in a sequence of such steps?

(5 pont)

Deadline expired on January 10, 2012.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

91 students sent a solution.
5 points:	Á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 points:	Á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 points:	19 students.
2 points:	7 students.
1 point:	30 students.
0 point:	10 students.
Unfair, not evaluated:	2 solutionss.

Problems in Mathematics of KöMaL, December 2011