Problem B. 3973. (February 2007)

B. 3973. In how many different ways is it possible to place 14 bishops on a chessboard so that they do not attack each other?

(3 pont)

Deadline expired on March 19, 2007.

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

Megoldás: Nevezzük átlónak a sakktábla azonos színű mezőinek olyan maximális részhalmazát, amelyek mindegyikén áthalad valamely, a tábla széleivel 45^o-os szöget bezáró egyenes. Ennek megfelelően megkülönböztetünk sötét és világos átlókat, egy adott átló hossza alatt az átlóban szereplő mezők számát értjük. Világos, hogy egy átlóban csak egy futó állhat. Mivel az összes világos mező beosztható 7 párhuzamos átlóba, melyek hossza rendre 2, 4, 6, 8, 6, 4, 2, és hasonló állítás igaz a sötét mezőkre is, a 14 futót csak úgy helyezhető el, ha pontosan 7 világos és 7 sötét bábu van köztük, az említett átlók közül mindegyikben pontosan egy.

Vizsgáljuk meg, hányféleképpen helyezhetjük el a 7 világos bábut, a 14 futó lehetséges elhelyezéseinek száma nyilván ennek a négyzete lesz. Az egyik 2 hosszú világos átló bármelyik mezőjére helyezhetünk egy bábut, ez a másik 2 hosszú világos átlóban elhelyezhető bábu helyzetét egyértelműen meghatározza. Ezek után a 4, 6, illetve 8 hosszú világos átlókban a középső két helyre már nem tehetünk bábut, vagyis az egyik 4 hosszú átlóban két hely közül választhatunk, és az a másik 4 hosszú átlóba elhelyezendő bábu helyét már eldönti. A gondolatmenetet folytatva látszik, hogy a 7 világos bábut 2⁴ lehetséges módon helyezhetjük el, az összeset pedig ezek szerint 2⁸=256 különböző módon.

Statistics:

187 students sent a solution.
3 points:	113 students.
2 points:	15 students.
1 point:	22 students.
0 point:	37 students.

Problems in Mathematics of KöMaL, February 2007