5. Zadatak

Polja jedinične kvadratne mreže velikih dimenzija obojana su naizmjenično crno i bijelo, poput šahovske ploče. Iz te mreže izrezan je poligon čije stranice leže na linijama kvadratne mreže. Neka se taj poligon sastoji od $B$ bijelih i $C$ crnih polja, a njegov rub od $b$ bijelih i $c$ crnih jediničnih dužina. Dokaži da vrijedi $c-b=4(C-B)$ .

Rješenje

Prvo rješenje.

Nazovimo unutrašnjima one jedinične dužine koje su stranice nekog kvadratića poligona, ali nisu na rubu poligona.

Neka je $u$ broj unutrašnjih dužina. Dokažimo da je $c+u=4C$ .

Službeni crtež šahovskog poligona

Na dva načina brojimo jedinične dužine koje su ujedno stranice crnih kvadratića.

Broj svih takvih dužina je $4C$ jer svaki kvadratić ima 4 stranice, a nikoja dužina šahovske ploče nije istovremeno stranica dva različita crna kvadratića.

S druge strane, svaka takva dužina je ili unutrašnja dužina ili crna dužina ruba poligona. Zato je ukupan broj unutrašnjih dužina i crnih dužina ruba jednak broju stranica svih crnih polja, tj. $c+u=4C$ .

Analogno, $b+u=4B$ . Oduzimanjem slijedi

4(C-B)=(c+u)-(b+u)=c-b.

Drugo rješenje.

Dokažimo tvrdnju matematičkom indukcijom po broju polja poligona.

Ako se poligon sastoji samo od jednog polja razlikujemo dva slučaja – to polje je crno ili bijelo. U prvom slučaju je $C=1$ , $c=4$ , $B=0$ , $b=0$ , a u drugom $B=1$ , $b=4$ , $C=0$ , $c=0$ pa tvrdnja u oba slučaja vrijedi.

Pretpostavimo da tvrdnja vrijedi za neki poligon $P$ i dokažimo da tada tvrdnja vrijedi za svaki poligon $P'$ koji možemo dobiti dodavanjem jednog polja poligonu $P$ .

Označimo s $C'$ , $B'$ , $c'$ , $b'$ redom brojeve crnih polja, bijelih polja, crnih rubnih dužina i bijelih rubnih dužina poligona $P'$ . Koristeći tvrdnju $4(C-B)=c-b$ želimo dokazati da je $4(C'-B')=c'-b'$ .

Ako je poligon $P'$ dobiven dodavanjem crnog polja, onda je $C'=C+1$ i $B'=B$ .

Svi susjedi tog crnog polja su bijela polja. Neka je $k$ broj stranica tog crnog polja koje su na rubu poligona ( $k$ može biti 0, 1, 2 ili 3). Dodavanjem tog crnog polja na rubu se pojavilo $k$ crnih dužina, a izgubili smo $4-k$ bijelih dužina, tj. $c'=c+k$ i $b'=b-(4-k)$ .

Zato je

4(C'-B')=4(C+1-B)=4(C-B)+4=c-b+4=(c'-k)-(b'+4-k)+4=c'-b',

što je i trebalo dokazati.

Analogno (zamjenom uloga bijele i crne boje) dokazujemo tvrdnju u slučaju da je $P'$ dobiven dodavanjem bijelog polja poligonu $P$ . Time je proveden korak indukcije i slijedi tvrdnja zadatka.