Matematické Fórum

↑ jelena:: má to platit pro šachovnici jakoukoliv nxn ... nemám žádné originální zadání, učitel nám to nadiktoval jen takhle... a ano, je to tak. Celou bílou + jeden černý růžek..

pripad 1) je parne. Ak prefarbujes stlpec/riadok kde je ciernych policok, tak ti ubudne ciernych a pribudne ciernych, t.j. celkovy pocet ciernych narastie o (moze byt zaporne). Kedze je parne, tak parita poctu ciernych sa nikdy nezmeni. Ak mas na zaciatku teda klasicku sachovnicu, t.j. su tam usporiadane na stridacku, tak pocet ciernych na zaciatku je cize parny a teda nikdy nemozes dostat neparny pocet ciernych nech robis co robis a jedna cierna v rozku, to je neparny pocet.

pripad 2) Pre je to trivialne.

pripad 3) Pre to asi tiez nepojde.

Takze je to takto:
Pre to trivialne ide a pre sa to neda. Dokaz by mohol ist takto.
V prvom rade si treba uvedomit, ze je jedno v akom poradi sa prefarbuje a teda aj nema zmysel prefarbovat jeden stlpec ci riadok viac ako raz. Teda staci povedat, ze ktore riadku a stlpce prefarbujeme. Dalej si mozme uvedomit, ze sachovnica sa da jednoducho prefarbit na cele biele pole, teda staci dokazat, ze cele biele pole sa neda prefarbit na biele pole s ciernym rozkom.

Teraz ak mame nejaku instrukci na farbenie, ktora vyzera nejak takto: r1,r3,s1,s5,...
co znamena, ze prefarbi 1. riadok, 3. riadok, 1. stlpec, 5. stlpec (kazde max raz!!)
tak si mozme vsimnut, ze pole (x,y) sa prefarbi prave vtedy ked je tam prave jedno z rx a sy.

Podme na to teda sporom: Nech existuje taka instrukcia co nam prefarbi biele pole na biele pole s ciernym rozkom (1,1). Kedze je (1,1) prefarbene tak je tam prave jedno z r1 a s1. Zo symetrie mozme predpokladat, ze to je r1. Kedze ale (1,2) nie je prefarbene a je tam r1, tak tam musi byt aj s2. A kedze ani (2,2) nie je prefarbene a je tam s2, tak tam musi byt aj r2. A kedze ani (2,1) nie je prefarbene a je tam r2 tak tam musi byt aj s1. Co je spor, lebo je tam r1 aj s1 a ma tam byt prave jedno z nich.

Ved to je tu velmi podstatne, ze na poradi nezalezi a teda ako dosledok zalezi iba na parite poctu prefarbeni, resp. staci uvazovat iba 0 alebo 1 prefarbenie daneho stlpca/riadku.

to, ze nezalezi na poradi si lahko mozes overit tak, ze si fixujes iba jedno pole sachovnice a pozeras sa na to, ze aku ma farbu a zistis, ze tomu policku je jedno v akom poradi prichadzali instrukcie. Prefarbi sa vzdy iba z bielej na ciernu , alebo z ciernej na bielu a to v pripade, ze instrukcia zahrnala jeho riadok alebo stlpec.

V rubikovej kocke sa policko moze prefarbit na 5 inych farieb a to na ktoru sa prefarbi zjavne velmi zalezi od toho ako su ofarbene ostatne policka a teda aj od toho ako sa prefarbovalo predtym.