PUMaC 2011 · 组合（B 组） · 第 6 题

PUMaC 2011 — Combinatorics (Division B) — Problem 6

[ 6 ] Let N be the number of ways to place 4 bishops on a 5 × 5 chessboard such that no 3 are on the same diagonal. Find the remainder when N is divided by 100. (Note: the length of a diagonal on a 5 × 5 chessboard can be 2, 3, 4, or 5.) n

解析

To find the answer, we can instead subtract the number of ways we can position 4 bishops such that at least 3 are bishops on a diagonal from the total number of cases. Also, since the 1 problem asks for the remainder of the answer divided by 100, we only need to keep track of the ( ) 25 last two digits for intermediate steps. There are in total ≡ 50 (mod 100) ways of placing 4 4 bishops on the board. • When there are 4 bishops on a diagonal, they are either on the main diagonals or the diagonals with length 4. There are ( ) 5 2 + 4 = 14 4 cases of this kind. • Otherwise, there are exactly 3 bishops on some diagonal. They can be on the main diagonals, the diagonals with length 4, or the diagonals with length 3. The number of cases can also be calculated: ( )( ) ( )( ) ( ) 5 20 4 21 22 2 + 4 + 4 ≡ 0 + 16 · 21 + 88 ≡ 24 (mod 100) . 3 1 3 1 1 Therefore, we obtain the final answer to be 50 − 14 − 24 = 12 .