PUMaC 2017 · 组合（A 组） · 第 7 题
PUMaC 2017 — Combinatorics (Division A) — Problem 7
题目详情
- If N is the number of ways to place 16 jumping rooks on an 8 × 8 chessboard such that each rook attacks exactly two other rooks, find the remainder when N is divided by 1000. (A jumping rook is said to attack a square if the square is in the same row or in the same column as the rook.)
解析
- We seek to establish a recursive formula for the number f ( n ) to place 2 n rooks on the board such that each rook attacks exactly two other rooks; note that for this to occur each row and column must contain exactly two rooks. Viewing the rooks as vertices in a graph and edges correspond to attacking, we see that any placement p can be broken down into some c ( p ) even-length cycles of rooks attacking one another; denote by f ( n, k ) the number of placements with c ( p ) = k . Note that given any placement p , we can choose n non-attacking rooks. The c ( p ) only way to do this is for every one of the cycles, we take every other rook, yielding 2 ways to do so. Suppose we are given n rooks on the main diagonal, and wish to add n more rooks, one per row and one per column (to obtain some placement q ). Let g ( n, k ) denote the number of ways to do this such that c ( q ) = k . Then, n ∑ g ( n, k ) = ( n − 1) · . . . · ( n − i + 1) · g ( n − i, k − 1) i =2 ( ) = ( n − 1) · g ( n − 2 , k − 1) + g ( n − 1 , k ) Given any placement p and choice of n non-attacking rooks, we can permute columns to get the n non-attacking rooks on the main diagonal. Thus, n ! f ( n, k ) = · g ( n, k ) k 2 ( ) n ! = · ( n − 1) · g ( n − 2 , k − 1) + g ( n − 1 , k ) k 2 ( ) ( ) n ( n − 1)! = · · g ( n − 2 , k − 1) + g ( n − 1 , k ) k − 1 2 2 ( ) ( ) n = · ( n − 1) · f ( n − 2 , k − 1) + 2 · f ( n − 1 , k ) 2 We solve the recursion: n ∑ f ( n ) = f ( n, k ) k =1 ( ) n ∑ ( ) n = · ( n − 1) · f ( n − 2 , k − 1) + 2 · f ( n − 1 , k ) 2 k =1 ( ) ( ) n = · 2 · f ( n − 1) + ( n − 1) · f ( n − 2) 2 We find that f (8) = 187530840, so the answer is 840 . Problem written by Bill Huang