2007 Indonesia MO Problems/Problem 5

Problem

Let $r$ , $s$ be two positive integers and $P$ a 'chessboard' with $r$ rows and $s$ columns. Let $M$ denote the maximum value of rooks placed on $P$ such that no two of them attack each other.

(a) Determine $M$ .

(b) How many ways to place $M$ rooks on $P$ such that no two of them attack each other?

[Note: In chess, a rook moves and attacks in a straight line, horizontally or vertically.]

Solution

For the first part, note that once one rook is placed, other rocks can not be in the same row or same column as the other rooks. Thus, the second rook can be in $r-1$ of the rows and in $s-1$ of the columns, and the $n^\text{th}$ rook can be in $r-n+1$ of the rows and in $s-n+1$ of the columns. Since $r-(n-1)$ and $s-(n-1)$ must be greater than $0$ for the rook to be on the board, $n$ can be at most $s$ or $r$ , and since a rook must be on a row and a column, $n$ must be at most the minimum of $s$ and $r$ . Thus, $M = \boxed{\min (r,s) }$ .

Because there are $M$ rooks on the board, the rooks would take up every row or column (whichever one is fewer), so we would consider the number of ways a rook can be on a given row or column (whichever one is fewer). For instance, if $s \ge r$ , the rook in the first row can be in $s$ columns, the one in second row can be in $s-1$ columns and so on until we reach run out of rows/have no more rooks that we can place. For example, if $s = 5, r = 3$ , we have $5 \cdot 4 \cdot 3$ . We are $2\cdot 1$ shy of $5!$ , and this is because we have two more columns than rows/rooks. Thus, the number of ways to place the rooks are: $\boxed{\frac{(max(r,s))!}{[max(r,s) - min(r,s)]!} = \frac{(max(r,s))!}{[max(r,s) - M]!} = ^{max(r,s)}P_M}$

2007 Indonesia MO (Problems)
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Problem 6
All Indonesia MO Problems and Solutions

Page

Toolbox

Search

2007 Indonesia MO Problems/Problem 5

Problem

Solution

See Also