5. Zadatak

Ne smanjujući općenitost možemo pretpostaviti da je $n\le p$. U kvadratni dio pravokutnika s lijeve strane postavimo crne kvadratiće na glavnu dijagonalu. Ako je $n<p$, u pravokutnik $n\times(p-n)$ u svaki drugi stupac u zadnji redak, počevši s desne strane, stavimo po jedan crni kvadratić. Lako je vidjeti da će dozvoljenim operacijama svi kvadratići postati crni. Ako su $n$ i $p$ iste parnosti onda je broj crnih kvadratića u ovom rasporedu jednak $n+\dfrac{p-n}2$, a ako su različitih parnosti ima ih $n+\dfrac{p-n+1}2$. Zato je $m\le\left\lfloor\dfrac{n+p+1}2\right\rfloor$. Pokazat ćemo da je $m=\left\lfloor\dfrac{n+p+1}2\right\rfloor$.

Segment na rubu je brid samo jednog kvadratića, dok je unutarnji segment brid dvaju kvadratića. Promatrat ćemo segmente koji pripadaju samo jednom crnom jediničnom kvadratiću. Sve ćemo takve segmente zvati rubnim segmentima. Kako na početku ima $m$ crnih kvadratića, tada (na početku) ima najviše $4m$ rubnih segmenata. Ako promijenimo bijeli kvadratić, koji je dodirivao $k$ crnih kvadratića, u crni, onda će nestati $k$ rubnih segmenata, a nastat će $4-k$ novih rubnih segmenata. Kako je operacija dozvoljena samo ako je $k\ge2$, imamo $4-k\le k$, tako da se broj rubnih segmenata ne povećava. Kada svi kvadratići prijeđu u crne, bit će $2(n+p)$ rubnih segmenata. Odavde slijedi $4m\ge2(n+p)$, ili $m\ge\dfrac{n+p}2$ tj. $m\ge\left\lfloor\dfrac{n+p+1}2\right\rfloor$.

Prema tome, $m=\left\lfloor\dfrac{n+p+1}2\right\rfloor$.