Feladat: Gy.2209 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Fazekas Ibolya 
Füzet: 1985/április, 164. oldal  PDF  |  MathML 
Témakör(ök): Egyéb szinezési problémák, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1984/szeptember: Gy.2209

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.

Rendeljük hozzá minden egyes kiszínezett mezőhöz a vele szomszédos kiszínezett mezők számát. Az így adódó számok összege páros, hiszen az összegzés során minden egyes szomszédságot pontosan kétszer számolunk.
A b) esetben így nincs megfelelő színezés, ugyanis a 25 páratlannak előírt szomszédság összege páratlan szám.
Az a) esetben több megoldást is kapunk, ezek közül kettő az ábrán látható.

 
 


Megjegyzés. Több megoldó ‐ tévesen ‐ úgy vélte, hogy az a) esetben már abból is következik a megfelelő színezés létezése, hogy a megadott szomszédságok összege páros. Ez azonban nem igaz, a feltétel csak szükséges. Könnyen igazolható, hogy ha azt írjuk elő, hogy minden egyes kiszínezett mezőnek pontosan két szomszédja legyen kiszínezve, akkor továbbra sem létezik megfelelő színezés.