Feladat: F.1941 Korcsoport: 18- Nehézségi fok: -
Füzet: 1974/szeptember, 29. oldal  PDF  |  MathML 
Témakör(ök): Kombinatorika, Konstruktív megoldási módszer, Feladat
Hivatkozás(ok):Feladatok megoldásai: 1975/március: F.1941

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.

Egy végtelen, fehér, négyzethálós papírlapon véges számú négyzet feketére van festve. A t=1, 2, ... időpillanatokban a papír összes négyzeteiben egyidejűen átszíneződés történik a következő szabályok szerint. Minden egyes ,,N'' négyzet olyan színűvé válik, amilyen volt az előző pillanatban a következő 3 négyzet többsége: maga az N négyzet, a jobb és a felső szomszédja (vagyis, ha ezek közül 2 vagy 3 fehér volt, akkor N fehérré válik, ha pedig 2 vagy 3 fekete volt, akkor feketévé válik).
Bizonyítsuk be, hogy véges idő múlva a papíron nem található fekete négyzet.