A B. 3862. feladat (2005. december)

B. 3862. Hányféleképpen lehet elhelyezni a 8×8-as sakktáblán 32 huszárt úgy, hogy semelyik kettő ne támadja egymást?

(4 pont)

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

1. Megoldás: Ha két huszár azonos színű mezőn áll, akkor nem támadják egymást. Ha tehát az összes huszárt azonos színű mezőre helyezzük, az jó megoldás lesz. Ez összesen két lehetőség. Megmutatjuk, hogy más megoldás nincs. Ehhez bontsuk fel a sakktáblát 2×2-es kis négyzetekre, két szomszédos kis négyzet egyesí tését pedig nevezzük el téglalapnak. Egy téglalap egyértelműen felbontható 4 páronkánt diszjunkt, egyenként két, lóugrásban elhelyezkedő mezőből álló részre, melyek mindegyikébe csak egy huszárt helyezhetünk. Könnyű látni, hogy akármelyik téglalapot kiegészíthetjük 7 további téglalappal úgy, hogy a sakktábla egy felbontását kapjuk, tehát minden egyes téglalapra pontosan 4 huszárt kell elhelyeznünk. Az is kiderül ebből, hogy ha egy téglalap egyik kis négyzetébe valamilyen elrendezésben néhány huszárt elhelyeztünk, akkor az a másik kis négyzetben álló huszárok elhelyezkedését már egyértelműen meghatározza. Ebből pedig már az is következik, hogy akarmelyik kis négyzetben elhelyezett huszárok helyzete meghatározza az egész elrendezést.

Szemeljünk ki egy kis négyzetet a sakktábla középső részéről. Világos, hogy ha ebbe a kis négyzetbe átlósan helyezünk el két huszárt, akkor az szükségképpen a fent említett két megoldás valamelyikéhez vezet. Tekintsünk bármely más elrendezést. Ha a kis négyzetbe kettőnél több huszárt helyeztünk el, akkor a vele szomszédos kis négyzetek mindegyikébe kettőnél kevesebb huszár kell, hogy legyen. Feltehető tehát, hogy a kiszemelt kis négyzetbe legfeljebb két huszár került. Egészítsük ki a kis négyzetet egy 4 kis négyzetből áló nagyobb négyzetté és vizsgáljuk meg, hogy a kis négyzetbe elhelyzett huszárok helyzete ezen milyen elrendezést indukál. Szimmetria okok miatt elegendő az ábrán látható három elhelyezést megvizsgálni, ahol a kiszemelt kis négyzet a nagyobb négyzet bal felső sarkában van. A huszárok helyzetét x jelöli, mindhárom esetben találunk végül két huszárt, melyek egymást támadják.

2. Megoldás: Ismeretes, hogy a sakktábla mezőit be lehet járni egy huszárral oly módon, hogy minden mezőre pontosan egyszer lépünk, majd végezetül visszalépünk a kiindulási mezőre. Egy ilyen körséta 64 ugrásból áll. Mivel két egymást követő mező nem szerepelhet az elrendezésben, a körsétából minden második mezőt kell kiválasztanunk, ezt pedig kétféleképpen tehetjük meg.

Statisztika:

199 dolgozat érkezett.
4 pontot kapott:	Csorba János, Dányi Zsolt, Gaizer Tünde, Károlyi Márton, Korándi Dániel, Lamm Éva, Láng Marcell, Lovász László Miklós, Nagy 314 Dániel, Paksy Patrik, Peregi Tamás, Pesti Veronika, Prőhle Zsófia, Szabó 108 Tamás, Szakács Nóra, Szalóki Dávid, Szilágyi 987 Csaba, Tossenberger Anna, Udvari Balázs, Varga 171 László.
3 pontot kapott:	Balambér Dávid, Bartha Zsolt, Blázsik Zoltán, Csató László, Dombi Soma, Károlyi Gergely, Kiss 243 Réka, Kristóf Panna, Kunovszki Péter, Mercz Béla, Mészáros Gábor, Nagy 235 János, Nagy-Baló András, Németh 007 Zsolt, Németh 546 Attila György, Örkényi Róbert, Páldy Sándor, Szalkai Balázs, Szőke Nóra, Wolosz János.
2 pontot kapott:	18 versenyző.
1 pontot kapott:	92 versenyző.
0 pontot kapott:	49 versenyző.

A KöMaL 2005. decemberi matematika feladatai