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 |