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 szóban forgó rácspontok sorban és oszlopban helyezkednek el. Nevezetesen, az -edik sor () azokat a rácspontokat tartalmazza, amelyeknek a második koordinátája . Hasonlóképpen, az -edik oszlop azokból a rácspontokból áll, amelyek első koordinátája . Két rácspontot szomszédosnak fogunk hívni akkor, ha ugyanabban a sorban vagy oszlopban egymás mellett helyezkednek el. Az pont szomszédai tehát az , , és pontok, amennyiben ezek is az négyzet pontjai. Nyilván jó színezését kapjuk a pontoknak akkor, ha minden sorban felváltva színezzük pirosra és zöldre az egymást követő pontokat. Az egyes sorokat ekkor egymástól függetlenül kétféleképpen színezhetjük, ezért az ilyen színezéseknek a száma . Ugyanilyen megfontolásból lesz jó az a színezés is, ahol az egyes oszlopokban követik egymást felváltva a piros és zöld pontok. Mivel a pontokat kétféleképpen lehet úgy kiszínezni, hogy sem a sorokban, sem az oszlopokban nincs két szomszédos azonos színű pont, ezért így összesen jó színezést találtunk. Megmutatjuk, hogy a fentieken kívül nincs más jó színezés. Ehhez tegyük fel először azt, hogy a pontokat megszíneztük a kívánt módon, és valamelyik oszlopban ‐ mondjuk az -edikben ‐ van egymás mellett két azonos színű szomszédos pont. Legyenek ezek és . Ekkor az -edik és az -edik oszlopban is található egymás mellett két azonos színű pont. Nevezetesen az , , , pontok mind azonos színűek, és egyben az , pontoktól eltérő színűek kell, hogy legyenek. Indukcióval könnyen ellenőrizhető ezután, hogy az , , , pontok színe az , pontokéval megegyező, ha páros, illetve azokétól eltérő, ha páratlan. Tegyük fel most még azt is, hogy valamelyik sorban ‐ mondjuk a -edikben ‐ is van egymás mellett két azonos színű pont: és . Az előbbihez hasonló gondolatmenettel (vagy egyszerűbben: szimmetria okokra hivatkozva) megállapíthatjuk, hogy minden -ra az , , , pontok azonos színűek. A fentiek szerint az pont színe meg kell, hogy egyezzen mind az , mind az pont színével. Ez azonban egy jó színezésben nem történhet meg, hiszen a felsorolt három pont éppen egy egységoldalú rácsnégyzet három csúcsa. Ez az ellentmondás igazolja azon állításunkat, miszerint minden jó színezésben vagy az oszlopokban, vagy a sorokban váltakozó színű pontok követik egymást. A kérdéses színezések száma tehát . |