HMMT 二月 2004 · GEN1 赛 · 第 4 题

HMMT February 2004 — GEN1 Round — Problem 4

How many ways can you mark 8 squares of an 8 × 8 chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked? (Rotations and reflections are considered different.) √

解析

How many ways can you mark 8 squares of an 8 × 8 chessboard so that no two marked squares are in the same row or column, and none of the four corner squares is marked? (Rotations and reflections are considered different.) Solution: 21600 In the top row, you can mark any of the 6 squares that is not a corner. In the bottom row, you can then mark any of the 5 squares that is not a corner and not in the same column as the square just marked. Then, in the second row, you have 1 6 choices for a square not in the same column as either of the two squares already marked; then there are 5 choices remaining for the third row, and so on down to 1 for the seventh row, in which you make the last mark. Thus, altogether, there are 6 · 5 · (6 · 5 · · · 1) = 30 · 6! = 30 · 720 = 21600 possible sets of squares. √