A B. 4661. feladat (2014. november)

B. 4661. Adott egy \(\displaystyle n\) oszlopot és \(\displaystyle k\) sort tartalmazó sakktábla, melynek bizonyos mezőire korongokat helyeztünk (minden mezőre legfeljebb egyet). Nevezzünk két korongot szomszédosnak, ha egy sorban vagy oszlopban vannak, és az őket összekötő szakaszon nincs további korong. Minden korongnak legfeljebb három szomszédja van. Legfeljebb hány korong van a sakktáblán?

Javasolta: Williams Kada (Szeged, Radnóti M. Kís. Gimn.)

(6 pont)

A beküldési határidő 2014. december 10-én LEJÁRT.

Megoldási ötlet: Vizsgáljuk azokat a pontokat, amiknek van jobb- és baloldali szomszédjuk is.

Megoldás. Ha minden korongnak legfeljebb három szomszédja van, vagyis legfeljebb három másik korongot ,,lát'' a táblán, akkor ez azt jelenti, hogy legalább egy irányban nincs szomszédja. Mondhatjuk úgy, kinéz a tábláról egy ablakon, ahol az ,,ablak'' a sakktábla kerületének egységnyi része.

Megállapíthatjuk, hogy a sarokba bármilyen elrendezés mellett elhelyezhető korong anélkül, hogy bármely más korong kilátását zavarná. Ez azért igaz, mert a szélső sorokban és oszlopokban álló korongok közvetlenül kilátnak a tábláról, hiszen egyik oldaluk a tábla kerületén van. A sarkokba elhelyezett négy korong összesen 8 ablakot takar el.

Ezután marad még \(\displaystyle 2(n+k)-8\) ablak. A legtöbb korongot akkor tudjuk elhelyezni, ha mindegyik pontosan egy ablakon lát ki. Ilyen elrendezés létezik, például ha az összes szélső mezőt korongokkal töltjük fel. Ebből további jó megoldásokat generálhatunk, a szélső korongok beljebb tologatásával, de újabb korongot már nem tudunk elhelyezni (ábra).

Megállapítható, hogy \(\displaystyle n,k\ge 2\) esetén a korongok száma legfeljebb \(\displaystyle 2(n+k) -4\) lehet. Ha \(\displaystyle n=1\) vagy \(\displaystyle k=1\), akkor legfeljebb annyi korong helyezhető el a táblán, ahány mező van, ilyenkor minden korongnak legfeljebb két szomszédja van.

Adorján Dániel (Budapest, Szent István Gimn., 10. évf.) dolgozata alapján

Statisztika:

109 dolgozat érkezett.
6 pontot kapott:	Adorján Dániel, Andó Angelika, Árvai Balázs, Bálint Martin, Balog Gergely, Baran Zsuzsanna, Bereczki Zoltán, Bertalan Dávid, Bursics Balázs, Csépai András, Csitári Nóra, Czirkos Angéla, Döbröntei Dávid Bence, Fekete Panna, Gáspár Attila, Glattfelder Hanna, Hansel Soma, Imolay András, Katona Dániel, Kerekes Anna, Khayouti Sára, Kovács 246 Benedek, Kovács 972 Márton, Kovács Péter Tamás, Kőrösi Ákos, Lajkó Kálmán, Leitereg Miklós, Mályusz Attila, Mócsy Miklós, Molnár-Sáska Zoltán, Nagy Dávid Paszkál, Nagy-György Pál, Németh Hanna, Porupsánszki István, Schrettner Bálint, Schwarcz Tamás, Szakács Lili Kata, Szebellédi Márton, Szőke Tamás, Tárkányi Damján, Vágó Ákos, Váli Benedek, Wei Cong Wu, Williams Kada.
5 pontot kapott:	28 versenyző.
4 pontot kapott:	5 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	21 versenyző.
0 pontot kapott:	6 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2014. novemberi matematika feladatai