Kezdőlap


Feladat:	Gy.2142	Korcsoport: 14-15	Nehézségi fok: átlagos
Füzet:	1984/április, 161 - 162. oldal		PDF \| MathML
Témakör(ök):	Egyéb szinezési problémák, Logikai feladatok, Gyakorlat
Hivatkozás(ok):	Feladatok: 1983/október: Gy.2142

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.

I. megoldás. Egy oszlop vagy egy sor átfestésekor pontosan 12 mező színe változik meg. Így ha átfestés előtt ott $f$ fehér mező volt, akkor az átfestés után $12 - f$ lesz. És mivel $f$ és $12 - f$ azonos párosságú, a sakktáblán található fehér mezők paritása az átfestések során nem változik.
Ezek szerint ha a sakktáblán a fehér mezők száma eredetileg páratlan volt, ez a szám minden átfestés után páratlan marad, és így nem érhető el, hogy a fehér mezők száma nulla, azaz páros legyen.

II. megoldás. A csupa fekete mezőjű sakktáblát pontosan azokból a színezésekből kiindulva lehet előállítani, amelyek a feketére festett táblákból nyerhetők a fent leírt módon. Az eljárás olyan, hogy a színezés sorrendje nem befolyásolja a végeredményt, másrészt ugyanannak a sornak, ill. oszlopnak kétszeri átfestése elhagyható. Így feltehető, hogy minden sort és oszlopot legfeljebb egyszer festünk át.
Az oszlopok és sorok együttes száma

24

, így összesen

2^{24}

módon jelölhetjük ki, hogy mely oszlopokat, ill. sorokat kell átfesteni, tehát legfeljebb

2^{24}

olyan színezése van a sakktáblának, amiből a csupa fekete mezőjű tábla előállítható.
Ugyanakkor a sakktábla

144

mezőjét

2^{144}

-féleképpen lehet két színnel kiszínezni, így a

2^{144} > 2^{24}

miatt van olyan színezés, amelyből nem érhető el, hogy minden mező fekete legyen. A feladat kérdésére a válasz: nem.

Megjegyzések. 1. Az I. megoldás mintájára igazolható a következő állítás. Ha elérhető, hogy valamennyi mező fekete legyen, akkor bárhogy veszünk ki két sort és két oszlopot, a metszéspontjaikban álló négy mezőből páros számúnak kell fehérnek lennie. Így például az ábrán látható táblából kiindulva nem érhető el a csupa fekete tábla, annak ellenére, hogy minden sorban és minden oszlopban páros sok fehér mező van.

A most megfogalmazott feltétel nemcsak szükséges, hanem elégséges is: ha teljesül, a fekete tábla elérhető.
2. Azt is könnyű meggondolni, hogy a "jó'' színezések száma nem

2^{24}

-

például ha mindegyik oszlopot és mindegyik sort átfestjük, ugyanazt érjük el, mintha nem festettünk volna semmit

-

, hanem

2^{23}