Kezdőlap


Cím:	Figurák a sakktáblán
Szerző(k):	Blázsik Zoltán
Füzet:	1995/november, 449 - 452. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

Szeptemberben ,,egymás kezét fogták'' a királyok, hosszú kört alkotva.^{$^{*}$} Egy ilyen láncnál szükséges feltétel, hogy semelyik $2 \times 2$ -es négyzetben se legyen 2-nél több király, hiszen ha lenne 3 király egy $2 \times 2$ -es négyzetben, akkor azok páronként szomszédosak lennének, egy háromszöget képeznének, ami nem lehetne egy hosszabb kör része.
Vajon legfeljebb hány figura tehető fel egy sakktábla mezőire, ha mindegyik $2 \times 2$ -es négyzetbe pontosan 2 figura kerülhet? Az erre a kérdésre adott válasz felső korlátja a ,,királyi kör'' hosszának. A $8 \times 8$ -as sakktáblán ilyen felső korlát a 32, hiszen felbontható 16 páronként diszjunkt $2 \times 2$ -es négyzetre. Másrészt a sakktábla szokásos pepita színezését használva pl. a világos mezőkre egy-egy figurát feltehetünk, tehát a 32-es határ éles. Természetesen nem következik mindebből, hogy léteznie kellene 32 hosszú ,,királyi körnek'', sőt tudjuk, hogy nincs is ilyen.*
Érdekes azonban a fenti kérdés általánosabb formája.

*	1.Legfeljebb hány figura helyezhető el egy $n \times n$ -es sakktáblára, ha bármelyik $k \times k$ -as négyzetben ( $k < n$ ) pontosan $i$ figurának kell állnia?

Nyilván az

n = 8

k = i = 2

esethez hasonlóan egyszerű a kérdés, ha

k ∣ n

, azaz

n = a k

alakú. Az biztos, hogy

{(\frac{n}{k})}^{2} i = a^{2} i

-nél többet nem lehet feltenni.
De vajon elhelyezhető-e ennyi? Az

n \times n

-es sakktáblán

{(n - k + 1)}^{2}

számú

k \times k

-s négyzet van. Ezek mindegyikébe pontosan

i

figurát kellene elhelyeznünk. Próbáljuk meg kis

n

-re,

k

-ra a bábukat ügyesen letenni! Először nehéznek tűnik a konstrukció. De ha a szőnyeg vagy a tapéta periodikusan ismétlődő mintáira gondolunk, hamar rájöhetünk, elég pl. a bal felső sarokban lévő

k \times k

-s négyzetbe

i

figurát tetszőlegesen elhelyezni, majd ezt

k

-asával jobbra is, lefelé is ismételni. Ezzel az

n = a k

esetet elintéztük.
Tegyük fel, hogy

n = a k + b

, ahol

1 \leq b < k

. Világos, hogy minden

a k \times a k

-s négyzetben

a^{2} i

figurának kell állnia, így pl. a jobb alsó

a k \times a k

-s négyzetben is. Azt kell elérnünk, hogy az ebből kimaradó részen (a peremen) a lehető legtöbb figura legyen. Ezért először is a bal felső

b \times b

-s négyzetbe annyi figurát helyezünk, amennyit csak lehet (legfeljebb

i

-t). Ha

i > b^{2}

, akkor további figurákat helyezhetünk el a perem és a bal felső

k \times k

-s négyzet közös részébe ‐ természetesen a már betöltött

b \times b

-s részen kívül (1. ábra). Ebbe a két

b \times (k - b)

-s téglalapba helyezzük a figurákat, amíg fér. A maradék (ha van) jut a

k \times k

-s négyzet

(k - b) \times (k - b)

-s részébe. Az így konstruált bal felső

k \times k

-s négyzetbeli kitöltés-mintát periodikusan ismételve egy maximális sok bábot tartalmazó

n \times n

-es négyzetet kapunk. (Gondoljuk meg, miért lesz ekkor minden

k \times k

-s négyzetben pontosan

i

darab figura!)

A maximum értéke:

{(a + 1)}^{2} \cdot i

i \leq b^{2}

a^{2} \cdot i + (2 a + 1) \cdot b^{2} + a {(i - b)}^{2} = (a + 1) \cdot (a \cdot i + b^{2})

b^{2} < i \leq k^{2} - {(k - b)}^{2}

és

a^{2} \cdot i + (2 n - b) \cdot b

i > k^{2} - {(k - b)}^{2}

Több irányban lehet tovább vizsgálódni. Ha megengedjük, hogy a sakktábla téglalap alakú legyen, akkor a fentihez teljesen hasonló meggondolás adja a következő eredményt: Ha a téglalap

n \times m

-es,

n = a \cdot k + b

(

1 \leq b < k

m = c \cdot k + d

(

1 \leq d < k

n \geq m

, akkor a maximum értéke

(a + 1) \cdot (c + 1) \cdot i

i \leq b \cdot d

a \cdot (c + 1) \cdot i + (c + 1) \cdot b \cdot d

b \cdot d < i \leq k \cdot d

(mert a figurákat téglalap esetén inkább a hosszabb oldal melletti ,,peremre'' érdemes helyezni).

a \cdot c \cdot i + n \cdot d + c \cdot (i - d (k - b))

k \cdot d < i \leq k (b + d) - b \cdot d

és

a \cdot c \cdot i + n \cdot d + m \cdot b - b d

i > k (b + d) - b d

Felvethető a minimum keresésének kérdése. Az erre adható válasz azonban következik a fentiekből, hiszen minden

i

-hez tartozó maximális jó figuraelhelyezés ,,komplementere'' egy

(k^{2} - i)

-hez tartozó minimális minta.
Csavarjuk most fel a téglalapot egy hengerre! Így csak alul és fölül lesz ,,pereme''. Egyáltalán lehetséges-e úgy figurákat felhelyezni a hengerre, hogy minden

k \times k

-s négyzetben ugyanannyi báb legyen? Ha igen, legfeljebb mennyit?
Ha pl. a henger legfelső részén egy

k \times k

-s négyzetet egyesével körbeléptetünk, akkor észrevehetjük, hogy a

k \times 1

-es oszlopokban lévő figurák száma

k

periódusonként ismétlődik. Amikor az ,,utolsó'' oszlophoz érünk, a felcsavarás miatt az elsővel folytatjuk. Ha

p = (n; k) = (b; k)

n

és

k

legnagyobb közös osztója, akkor az oszlopokban álló figurák számának sorozata

p

szerint periodikus kell legyen. Ebből azonnal következik egy szükséges feltétel

i

-re:

\frac{k}{p} | i

.
A hengeren, ha egy

k \times p

-s téglalapban tetszőlegesen

\frac{i \cdot p}{k}

figurát helyezünk el, majd ezt ismételjük mindkét irányban, akkor a ,,szőnyegminta'' a hengeren záródik. A szükséges

k ∣ i \cdot p

feltétel tehát elégséges is.
A maximum értéke:

n \cdot (c + 1) \cdot \frac{i}{k}

i \leq d \cdot k

n \cdot d + n \cdot c \cdot \frac{i}{k}

i > d \cdot k

ismét optimálisan kihasználva a henger alsó (vagy felső) peremét.
Hogyan kaphatnánk egy perem nélküli esetet, amikor minden mező ,,egyenrangú''? Hajtsuk össze a sakktáblánkat tórusszá! (Mintha mentőövet alakítanánk ki egy

n \times m

-es téglalapból.)
Gondolkozzunk el a további problémákon:

*	2.Mi a szükséges és elégséges feltétele annak, hogy egyáltalán létezzen egy ,,egyenletes'' figuraelhelyezés a toroidális sakktáblán?

*	3.A tórusznak nincs pereme. Vajon igaz-e, hogy minden olyan elrendezés, amelynél bármely $k \times k$ -s négyzetbe $i$ darab bábu kerül, ugyanannyi figurát használ fel?

Eddig arra törekedtünk, hogy ,,lokálisan kiegyensúlyozott'' bábufelrakásnál elérjük a figurák számának maximumát. Engedjünk a feltételből, illetve módosítsuk azt.

*	4.Adott $n$ , $m$ és $k$ . Legyen $1 \leq i < j \leq k^{2}$ . Mennyi a táblára helyezhető figurák számának maximuma, ha minden $k \times k$ -s négyzetbe legalább $i$ és legfeljebb $j$ bábut tehetünk?

*	5.Adott $n$ , $m$ és $k$ -ra milyen $(i; j)$ számpárra létezik olyan bábufelállítás, amikor mindegyik $k \times k$ -s négyzetben vagy pontosan $i$ , vagy pontosan $j$ darab figura van, és létezik legalább egy olyan $k \times k$ -s négyzet, amiben $i$ darab van, és olyan is, amiben $j$ darab van.

*	6.Vajon mikor létezhet az $n \times m$ -es sakktáblán olyan elrendezés, hogy minden $k \times k$ -s négyzetben más-más számú figura legyen?

*	7.Létezik-e olyan alkalmas $n$ , $m$ és $k$ , hogy az $n \times m$ -es téglalap $k \times k$ -s négyzeteiben éppen rendre

a) 1, 2, 3, 4,

...

, 1995
b) 1, 2, 3, 4,

...

l

bábu álljon? (2. ábra)
(A 2. ábra az

n = m = 8

k = 6

l = 9

esetre mutat két megoldást; a baloldali a minimális 9, a jobb pedig 13 bábuval. Mennyi a maximum ebben az esetben?)

\begin{matrix} ⋆ \end{matrix}

A cikkhez a hozzászólásokat, a feladatok megoldásait (nemcsak a versenyzőktől) a szerkesztőség címén várja a szerző. A borítékra írják rá: ,,Figurák a sakktáblán''.

Blázsik Zoltán

^{$^{*}$}ld. a Királyok körei c. cikket az 1995/6. sz. 338. oldalán.