Maths Olympiad Prep

Library / /979 of 1394

, 2020

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Given an 8×88 \times 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?

Solution

Solution:

Number both the rows and the columns from 11 to 88, 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,82, 4, 6, 8. Choosing 88 squares all in different rows and columns is equivalent to matching rows to columns.

For each of the 88 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 44 squares of each color, the 44 rows matched to same-parity columns must contain 22 even rows and 22 odd rows. There are (42)2=62\binom{4}{2}^{2} = 6^{2} ways to choose 22 odd rows and 22 even rows to match with same-parity columns.

After choosing the above, we have fixed which 44 rows should be matched with odd columns (while the other 44 should be matched with even columns). Then there are (4!)2=242(4!)^{2} = 24^{2} ways to assign the columns to the rows, so the answer is (624)2=1442=20736(6 \cdot 24)^{2} = 144^{2} = 20736.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.