Very beatiful problem Answer: For $1 \times n$ and or $n \times 1$ obviously is $n$. For $m$ and $n$ greater than $1$ is $2m+2n-4$. We will consider a graph $G$, where the vertices are the red squares and we will put an edge between two squares $X$ and $Y$ if $X$ and $Y$ are in the same diagonal and there are not red squares between them. Now, note that there is a cycle on $G$ if only if there is a bishop circuit. For it, you can use that if the cycle has some $k$ vertices in the same diagonal then in the bishop path use the vertices at the extrems. We conclude that it's necessary that $G$ is a tree (or a forest) and is well-known that has $n-i$ edges, where $i$ is the number of conex components. Also see that if we paint the squares of the board like a chess with black and white we get that no one black square has edge with no one white square, so the graph has at least two trees, then the number of edges is at the most $N-2$. Now, enumerate the rows of the board with $1, 2, \dots, m$ and the columns with $m+1, m+2, \dots, m+n$. We will say that a diagonal is increasing if its beginning is on one of the left or bottom sides of the board and its end is on one of the top or right sides of the board. We will say that a diagonal is decreasing if its beginning is on one of the left sides or top and if its end is on one of the right or bottom sides. Those diagonals can be with lenght $1$ (vertices of the board) Let $a_i$ the number of red squares on the diagonal increasing that passes by the line with number $i$. Let $b_i$ the number of red squares on the diagonal decreasing that passes by the line with number $i$. Note that, by double counting $\sum a_i=\sum b_i=N$, where $N$ is the number of red squares on the board. The number of edges on the graph for each diagonal is $a_i-1$ (or $b_i-1$). So by double counting for the edges of the graph we have that: $$\sum_{i=1}^{m+n-1} a_i+\sum_{i=1}^{m+n-1} b_i-2(m+n-1)\leq N-2$$ We conclude that $N \leq 2m+2n-4$. The example ($m\leq n$) is paint all squares on the first and last column and on the last two rows.

I think your example in board 5. 5 is wrong. We have the midpoints in 4 sides make the bishop circuit

Also in (2n+1). (2n+1)

edfearay123 wrote: Very beatiful problem Answer: For $1 \times n$ and or $n \times 1$ obviously is $n$. For $m$ and $n$ greater than $1$ is $2m+2n-4$. We will consider a graph $G$, where the vertices are the red squares and we will put an edge between two squares $X$ and $Y$ if $X$ and $Y$ are in the same diagonal and there are not red squares between them. Now, note that there is a cycle on $G$ if only if there is a bishop circuit. For it, you can use that if the cycle has some $k$ vertices in the same diagonal then in the bishop path use the vertices at the extrems. We conclude that it's necessary that $G$ is a tree (or a forest) and is well-known that has $n-i$ edges, where $i$ is the number of conex components. Also see that if we paint the squares of the board like a chess with black and white we get that no one black square has edge with no one white square, so the graph has at least two trees, then the number of edges is at the most $N-2$. Now, enumerate the rows of the board with $1, 2, \dots, m$ and the columns with $m+1, m+2, \dots, m+n$. We will say that a diagonal is increasing if its beginning is on one of the left or bottom sides of the board and its end is on one of the top or right sides of the board. We will say that a diagonal is decreasing if its beginning is on one of the left sides or top and if its end is on one of the right or bottom sides. Those diagonals can be with lenght $1$ (vertices of the board) Let $a_i$ the number of red squares on the diagonal increasing that passes by the line with number $i$. Let $b_i$ the number of red squares on the diagonal decreasing that passes by the line with number $i$. Note that, by double counting $\sum a_i=\sum b_i=N$, where $N$ is the number of red squares on the board. The number of edges on the graph for each diagonal is $a_i-1$ (or $b_i-1$). So by double counting for the edges of the graph we have that: $$\sum_{i=1}^{m+n-1} a_i+\sum_{i=1}^{m+n-1} b_i-2(m+n-1)\leq N-2$$ We conclude that $N \leq 2m+2n-4$. The example ($m\leq n$) is paint all squares on the first and last column and on the last two rows. Your example is wrong when the board (2n+1).(2n+1)

graph theory

Lemma:If graph $G$ has $n$ vertices and at least $n$ edges, then this graph has a cycle. proof is easier than induction. Lemma:If the degree graph $G$ is at least two, this graph has a cycle.

An other approach, consider the graph $G$ where the vertices are the $2m+2n-2$ diagonals on the board. We put an edge between two diagonals $D_1,D_2$ if their intersection is a red square. It simple to show that there is a bishop circuit if and only if there is a cycle. Also if we color the vertices like a chessboard we see that every time we traverse an edge our color is the same, and thus the graph has at least two connected components. It follows that $e\leq 2n+2m-4$, where $e$ is the number of edges (i.e the number of red squares). For the example see edfearay123's solution.

Aegaertargaryen1102 wrote: I think your example in board 5. 5 is wrong. We have the midpoints in 4 sides make the bishop circuit Sorry, I didn't notice this message. With "the last two rows", I mean rows $m-1$ and $m$ and columns are $1$ and $n$.