KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 3862. (December 2005)

B. 3862. In how many different ways is it possible to place 32 knights on a 8×8 chessboard, such that no pair of them should attack each other?

(4 pont)

Deadline expired on 16 January 2006.


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

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.


Statistics:

199 students sent a solution.
4 points: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 points: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 points:18 students.
1 point:92 students.
0 point:49 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley