Van 12 pontunk,3x4 es rácsot alkotva. Bizonyítsd be, hogy két színt felhasználva piros és kék, ha minden pontot beszinezünk valamilyen színnel, akkor találunk olyan téglalapot, amelynek minden csúcsa egyszínű. Hogyan kell bizonyítani?

PPK

PKK

KPP

KKP

Állítás cáfolva.

Vagy:

PPP

PKK

KKP

KPK

Állítás cáfolva.

Például így; tekintsük a 3-as sorokat/oszlopokat (rajzolástól függően). Ezeket két színnel (pirossal és kékkel) 2*2*2=8-féleképpen lehet kiszínezni. Akkor lesz biztosan téglalap, hogyha két sorban/oszlopban ugyanazok a mezők vannak ugyanarra a színre festve, például PKP és PPP. Arra nem nehéz rájönni, hogyha legalább 2 sor/oszlop ugyanolyanra vannak festve, akkor ott található lesz megfelelő téglalap, így azt az esetet vizsgáljuk, amikor mindegyik különböző módon van befestve.

Intuitíven lehet érezni, hogyha valamelyik csak 1 színnel van lefestve (PPP vagy KKK), akkor nagyobb eséllyel fogunk találni téglalapot. Ha mindkét 3-as színezés megtalálható, akkor biztosan lesz, mivel minden oszlopban van legalább 2 valamelyik színből. Ha csak az egyik van, például PPP, akkor a PPK, PKP, KPP színezések alkotnak vele téglalapot. Ha ezeket nem használjuk, akkor marad 3 színezés (KKP, KPK, PKK), ezekkel kellene 6-ot lefesteni, láthatóan lehetetlen. Tehát ha van egyszínű sor/oszlop, akkor biztosan lesz téglalap.

Ha nem használunk egyszínűt, akkor marad 6 színezés, amivel 7-et kellene lefesteni, ez sem fog sikerülni úgy, hogy ne használjuk ugyanazt a színezést legalább kétszer.

Több lehetőség nincs, tehát akárhogyan okoskodunk, mindig lesz téglalap.