HMMT 二月 2020 · COMB 赛 · 第 4 题

HMMT February 2020 — COMB Round — Problem 4

Given an 8 × 8 checkerboard with alternating white and black squares, how many ways are there to choose four black squares and four white squares so that no two of the eight chosen squares are in the same row or column?

解析

Given an 8 × 8 checkerboard with alternating white and black squares, how many ways are there to choose four black squares and four white squares so that no two of the eight chosen squares are in the same row or column? Proposed by: James Lin Answer: 20736 Solution: Number both the rows and the columns from 1 to 8, and say that black squares are the ones where the rows and columns have the same parity. We will use, e.g. “even rows” to refer to rows 2, 4, 6, 8. Choosing 8 squares all in different rows and columns is equivalent to matching rows to columns. For each of the 8 rows, we first decide whether they will be matched with a column of the same parity as itself (resulting in a black square) or with one of a different parity (resulting in a white square). Since we want to choose 4 squares of each color, the 4 rows matched to same-parity columns must ( ) 2 4 2 contain 2 even rows and 2 odd rows. There are = 6 ways to choose 2 odd rows and 2 even rows 2 to match with same-parity columns. After choosing the above, we have fixed which 4 rows should be matched with odd columns (while the 2 2 other 4 should be matched with even columns). Then there are (4!) = 24 ways to assign the columns 2 2 to the rows, so the answer is (6 · 24) = 144 = 20736.