4. Zadatak

Definirajmo da je dužina važna ako su joj oba krajnja vrha iste boje.

Ukupan broj jediničnih kvadrata kojima su sva četiri vrha u $S$ je jednak $AB$. Označimo te jedinične kvadrate indeksima od 1 do $AB$. Za svaki od tih kvadrata definirajmo $b_i$ kao broj važnih dužina u $i$-tom jediničnom kvadratu. Očito je $b_i \in \{0,1,2,3,4\}$. Nadalje, nemoguće je da vrijedi $b_i=3$: ako su sva četiri vrha jediničnog kvadrata iste boje, tada je $b_i=4$, a inače je nužno $b_i \leq 2$. Primijetimo da je kvadrat poseban ako i samo ako vrijedi $b_i=1$.

Definirajmo broj $N:=b_1+\cdots+b_{AB}$. U toj sumi jedini neparni pribrojnici su oni za koje je $b_i=1$. Zato vrijedi: $N$ je paran ako i samo ako je broj posebnih jediničnih kvadrata paran.

S druge strane, u definiciji broja $N$ prebrojili smo sve važne dužine po svim jediničnim kvadratima u kojima se one nalaze. Svaka važna dužina koja se nalazi na rubu pravokutnika pripada točno jednom jediničnom kvadratu, dok se sve ostale važne dužine nalaze u točno dva jedinična kvadrata.

Neka je $a_u$ broj važnih dužina kojima se barem jedan vrh nalazi u unutrašnjosti pravokutnika, te $a_v$ broj važnih dužina koje se nalaze na rubu pravokutnika. Zbog prethodnog pasusa zaključujemo da vrijedi $N=a_v+2a_u$. Nadalje, sve dužine na rubu pravokutnika su važne (jer su im obje krajnje točke crvene), pa vrijedi $a_v=2(A+B)$, odnosno $N=2(A+B+a_u)$. Dakle, $N$ je paran, iz čega zaključujemo da je broj posebnih jediničnih kvadrata paran, što je i trebalo dokazati.