PUMaC 2010 · 组合（B 组） · 第 7 题
PUMaC 2010 — Combinatorics (Division B) — Problem 7
题目详情
- We say that a rook is “attacking” another rook on a chessboard if the two rooks are in the same row or column of the chessboard and there is no piece directly between them. Let n be the maximum number of rooks that can be placed on a 6 × 6 chessboard such that each rook is attacking at most one other. How many ways can n rooks be placed on a 6 × 6 chessboard such that each rook is attacking at most one other?
解析
- We say that a rook is “attacking” another rook on a chessboard if the two rooks are in the same row or column of the chessboard. Let n be the maximum number of rooks that can be placed on a 6 × 6 chessboard such that each rook is attacking at most one other. How many ways can n rooks be placed on a 6 × 6 chessboard such that each rook is attacking at most one other? Answer: 8100 Solution: Consider the following arrangement of rooks, where an R represents a rook: R R R R R R R R In this arrangement, each rook attacks at most one other, so n ≥ 8. Suppose there is such an arrangement of 9 rooks. Each row has at most 2 rooks, so there must be some 3 rows with exactly 2 rooks each. Call these 6 rooks “strong.” Suppose there are two strong rooks in the same column of the chessboard. Then these rooks each attack both each other and the strong rooks they share a row with, a contradiction. Therefore, the strong rooks all occupy different columns, so there is a strong rook in each column. Since there are only 6 strong rooks, there must be some rook R on the chessboard that is not strong. Take the strong rook that is in the same column as R . This strong rook attacks both R and the strong rook it shares a row with, a contradiction. Therefore there is no such arrangement of 9 rooks, so n = 8. Consider arrangements of 8 rooks. Since each row has at most 2 rooks, there are exactly 2 rows with 2 rooks and 4 rows with 1 rook. Similarly, there are exactly 2 columns with 2 rooks and 4 columns with 1 rook. The rooks in the rows with 2 rooks must have their own columns, 4 so these are the 4 columns with 1 rook. Call these 4 rooks the “row” rooks. Similarly, the rooks in the columns with 2 rooks are the rooks in the rows with 1 rook. Call these 4 rooks the “column” rooks. Therefore we can produce an arrangement by choosing the 2 rows that are to have 2 rooks and the 2 columns that are to have 2 rooks. The row rooks are in these 2 rows and in the other 4 columns, and the column rooks are in these 2 columns and in the other 4 rows. We finish constructing the arrangement by choosing 2 of the other 4 columns to contain the upper-most row of row rooks and 2 of the other 4 rows to contain the left-most column of column rooks. ( ) ( ) 2 2 6 4 Therefore the answer is = 8100 . 2 2