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 $r \ge s$ , then the rook in the first column can be in $r$ of the rows, the rook in the second column can be in $r-1$ of the rows, and so on. Similarly, if $r < s$ , then the rook in the first row can be in $s$ of the columns, the rook in the second row can be in $s-1$ of the columns, and so on. Therefore, the number of ways to place $M$ rooks on the board is $\boxed{\frac{(\max (r,s) )!}{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