2007 Indonesia MO Problems/Problem 5
Problem
Let ,
be two positive integers and
a 'chessboard' with
rows and
columns. Let
denote the maximum value of rooks placed on
such that no two of them attack each other.
(a) Determine .
(b) How many ways to place rooks on
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 of the rows and in
of the columns, and the
rook can be in
of the rows and in
of the columns. Since
and
must be greater than
for the rook to be on the board,
can be at most
or
, and since a rook must be on a row and a column,
must be at most the minimum of
and
. Thus,
.
Because there are 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
, then the rook in the first column can be in
of the rows, the rook in the second column can be in
of the rows, and so on. Similarly, if
, then the rook in the first row can be in
of the columns, the rook in the second row can be in
of the columns, and so on. Therefore, the number of ways to place
rooks on the board is
.
See Also
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 |