Feladat: Gy.1951 Korcsoport: 14-15 Nehézségi fok: átlagos
Füzet: 1981/november, 138 - 139. oldal  PDF file
Témakör(ök): Kombinatorikai leszámolási problémák, Sakktáblával kapcsolatos feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1981/január: Gy.1951

Hány lovat helyezhetünk el a 8×8-as sakktáblán úgy, hogy semelyik kettő ne üsse egymást ? Mi a helyzet az 5×5-ös sakktáblán ?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A sakktáblán a ló fehér mezőről feketére, feketéről pedig fehérre lép. Ez azt jelenti, hogy azonos színű mezőkön álló lovak közül semelyik kettő sem üti egymást. A 8×8-as sakktáblán 32 fekete és 32 fehér mező van, így itt 32 ló elhelyezhető a kívánt módon, ha például a fehér mezőkre állítjuk őket. Az 5×5-ös sakktáblán az egyik színből 12, a másikból pedig 13 mező van, ezen a táblán tehát legalább 13 ló helyezhető el.

 
1. ábra
 
2. ábra

Felállítható-e a táblákra a fentieknél több ló is az adott feltétellel?
Tekintsünk egy 2×4-es táblarészletet. Az itt található 8 mező 4 számmal megszámozható úgy, hogy az azonos számú mezőkön álló lovak üssék egymást. Egy ilyen számozást mutat az 1. ábra. Így egy ilyen részletre négynél több ló nem kerülhet, hisz különben feltétlenül volnának azonos számú mezőkön álló, tehát egymást ütő lovak. Mivel pedig a 8×8-as sakktábla felépíthető 8 darab 2×4-es részből, így 8×4=32-nél több ló már nem lehet a táblán. Fenti eredményünk tehát a lehető legjobb.
 

3. ábra
 

Az 5×5-ös tábla nem rakható össze 2×4-es téglalapokból, így itt más módszerre van szükség. A 2. ábrán 1-től 25-ig megszámoztuk az 5×5-ös tábla mezőit. Könnyen ellenőrizhető, hogy ha egy ló az 1. számú mezőről kiindulva mindig a soron következő számú mezőre lép, akkor 25 lépésben minden mezőt érint. Így ha 13-nál több lovat állítunk fel az 5×5-ös táblára, akkor ezek közt feltétlenül lesz legalább kettő, amelyek szomszédos sorszámú mezőkre kerülnek, tehát a számozás tulajdonsága miatt ütik egymást. Az 5×5-ös táblán tehát 13 ló elhelyezhető a kívánt módon, annál több már nem.
 

Megjegyzés. Az utóbbi módszer a 8×8-as tábla esetén is megadja a megfelelő felső határt, ha felhasználjuk azt az ismert tényt, hogy egy 8×8-as sakktábla is bejárható lóugrásokkal. Ilyen bejárást adunk meg a 3. ábrán.