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 tochoose 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 tochoose 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 oneswhere 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 parityas 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
( )
contain 2 even rows and 2 odd rows. There are = 6 ways to choose 2 odd rows and 2 even rows 242
to match with same-parity columns.2
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.