MathDB

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}

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

Problem Statement