rooks on chessboard

outback · Riemann Hypothesis Offline Joined: 18 Sep 2008 Posts: 294

On some fields of an $m\times n$ ( $m,n\geq 2$ ) chessboard rooks are being placed. It is known that every rook is attacked by at most two other rooks.
Determine the largest possible number of placed rooks for which such a situation is possible.

**Posted:** Thu Oct 16, 2008 3:49 pm

dysfunctionalequations

Is it m+n-1? I would put rooks on the top and right borders, as a rook cannot attack "through" another piece.

**Posted:** Thu Oct 16, 2008 5:26 pm

_________________
"You need to get fatter." - pythag011

outback · Riemann Hypothesis Offline Joined: 18 Sep 2008 Posts: 294

**Posted:** Thu Oct 16, 2008 5:50 pm

JBL

Ah, the magic of casework (coupled with bad presentation -- sorry!). Drawing some diagrams would help make sense of this.

Let $M(m, n)$ be the number we're looking for. I claim that $M(m, n) = m + n$ , and we'll prove it by induction. We can certainly achieve it for any $m, n \geq 2$ : take herefishyfishy's suggestion and add another square to the lower-left corner. Now if $m = 2$ (or $n = 2$ ), note that at most two of the rows (columns) of length 2 may have two rooks in them, so $m + n$ is an upper bound in this case. Then we've settled the base case.

Suppose we have a rook not attacked by any other. Then it's all alone it its row and column and we have a total of at most $1 + M(m - 1, n - 1)$ rooks. This is $m + n - 1$ by the inductive hypothesis, never larger than $m + n$ .

Suppose we have a rook attacked by only a single other rook. There must be at least two rooks attacked by only a single rook. If these two rooks happen to lie in the same row or column, no other rooks lie in the same row or column as either of these and we have a total of at most $\max\{2 + M(m - 1, n - 2), 2 + M(m - 2, n- 1)\} = m + n - 1$ rooks, again clearly not optimal. If instead these two rooks lie in different rows and columns, they lie at opposite corners of a rectangle. But then of the two squares at the other corners of the rectangle, (a) at most one has a rook in it, and (b) each is attacked by at most two rooks. So we can add a rook to the board while still satisfying the conditions, and our situation is not maximal.

So, if we have a maximal arrangement then every rook is attacked by exactly two others. We again have two cases: if there are three or more rooks in the same row (or column), the middle one(s) is alone in its column (or row) and so we have at most $1 + M(m, n - 1) = m + n$ rooks. Otherwise, each row and each column contains at most two rooks. Thus, there are a total of at most $\frac{1}{2}(2m + 2n) = m + n$ rooks on the board. And we're done.

**Posted:** Fri Oct 17, 2008 10:18 am

_________________
Joel
Hi Deeps! <3