MEMO 2021 I2

Let $m$ and $n$ be positive integers. Some squares of an $m \times n$ board are coloured red. A sequence $a_1, a_2, \ldots , a_{2r}$ of $2r \ge 4$ pairwise distinct red squares is called a bishop circuit if for every $k \in \{1, \ldots , 2r \}$ , the squares $a_k$ and $a_{k+1}$ lie on a diagonal, but the squares $a_k$ and $a_{k+2}$ do not lie on a diagonal (here $a_{2r+1}=a_1$ and $a_{2r+2}=a_2$ ). In terms of $m$ and $n$ , determine the maximum possible number of red squares on an $m \times n$ board without a bishop circuit. (Remark. Two squares lie on a diagonal if the line passing through their centres intersects the sides of the board at an angle of $45^\circ$ .)