Click to reveal hidden text

Great problem! Case 1: If $m,n\ge 3$, then the answer is $\boxed{2m+2n-8}$ For construction, let $c_{i,j}$ denote the cell in $i\text{-th}$ row and $j\text{-th}$ column. Place rooks in $c_{1,1},c_{1,2},\ldots,c_{1,n},c_{2,2},c_{2,3},\ldots,c_{2,n-1},c_{3,2},c_{4,2},\ldots,c_{m-1,2},c_{3,n-1},c_{4,n-1},\ldots,c_{m-2,n-1},c_{m,n-1}$ Now let's prove the bound. Consider $2m+2n$ rays, each starting from a unit edge at the border of our chessboard and each coming directly into the chessboard. Each ray continues untill it intersects a rook(If that row or column was empty, the ray will go out of the chessboard). Note that a rook will be attacked by odd number of other rooks, if and only if odd number of rays intersect at that rook. Let $A$ be the number of rooks that $3$ rays intersect at them and let $B$ be the number of rooks that only $1$ ray intersect them. Then $$\text{The number of rays}=2m+2n\ge 3A+B$$Note that we have placed $A+B$ rooks and If we prove that $A\ge 4$, we can get that $A+B\le 2m+2n-2\times4=2m+2n-8$. Now consider each rook as a point in the center of the cell that is located in it. Let $\mathcal{P}$ be the convex hull of the rooks(the points). Note that each vertex of the convex polygon $\mathcal{P}$ should have $3$ rays intersecting it. So if we prove that $\mathcal{P}$ has at least $4$ vertices, we are done. The cases that $\mathcal{P}$ has $1$ or $2$ vertices are easy to check. If $\mathcal{P}$ has exactly $3$ vertices, Note that we may assume that we don't have any empty row or column, because if a row is empty, then the two rays that pass through that row, don't intersect any rook so by deleting those two rays, we get that $A+B\le 2m+2n-8$. Consider the first and the last row and the first and the last column. Since we assumed that each of them has at least one rook, we can get that one of the rooks which were vertices of $\mathcal{P}$, is located in the intersection of one of those rows with one of those columns(in other words, it is located in one of the $4$ corners of the chessboard). By some easy casework, we get that two of the corner cells of the chessboard must have a rook. WLOG let them be at $c_{1,1}$ and $c_{1,n}$ and let the third vertex of $\mathcal{P}$ be at $c_{m,k}$. If the rightmost or the leftmost rook of the $(m-1)\text{-th}$ row are not $c_{m-1,k}$ then we are done since if the leftmost is not under that cell, then it should have $3$ rays intersecting it and so the number of rooks having $3$ rays, is at least $4$ and we are done. Since the $(m-1)\text{-th}$ row should have at least one rook, we get that it should have only one rook that is located in $c_{m-1,k}$. Again this rook should have $3$ rays and thus $A\ge 4$ and we are done. So we've proved that $A\ge 4$ in all cases thus the bound is proved. Case 2: If $m=2$, then the answer is $\boxed{2n-4}$. It can be checked by arguments similar to above.

Example constructions for $\boxed{2m+2n-8}$ [asy][asy] size(6cm); real a = 1.0, b = 1.0; int m = 7, n = 8; real w = a*m, h = b*n; pen color = RGB(80, 80, 255); void fill_cell(int row, int column, pen color) { filldraw(circle((row + 0.5, column + 0.5), 0.3), color); } for (int i = 2; i < m; ++i) { fill_cell(i, 1, color); } for (int i = m-3; i > -1; --i) { fill_cell(i, n-2, color); } for (int i = 0; i < n-2; ++i) { fill_cell(1, i, color); } for (int i = n-1; i > 1; --i) { fill_cell(m-2, i, color); } for (int i = 0; i < n+1; ++i) { draw((0, i*b) -- (w, i*b), linewidth(1.0pt)); } for (int i = 0; i < m+1; ++i) { draw((i*a, 0) -- (i*a, h), linewidth(1.0pt)); } [/asy][/asy] and [asy][asy] size(6cm); real a = 1.0, b = 1.0; int m = 7, n = 8; real w = a*m, h = b*n; pen color = RGB(80, 80, 255); void fill_cell(int row, int column, pen color) { filldraw(circle((row + 0.5, column + 0.5), 0.3), color); } for (int i = 0; i < m; ++i) { fill_cell(i, n-1, color); } for (int i = 2; i < m-2; ++i) { fill_cell(i, n-2, color); } for (int i = 2; i < n-1; ++i) { fill_cell(1, i, color); fill_cell(m-2, i, color); } fill_cell(1, 0, color); fill_cell(m-2, 1, color); for (int i = 0; i < n+1; ++i) { draw((0, i*b) -- (w, i*b), linewidth(1.0pt)); } for (int i = 0; i < m+1; ++i) { draw((i*a, 0) -- (i*a, h), linewidth(1.0pt)); } [/asy][/asy]