Maths Olympiad Prep

Library / /210 of 462

, 2014

Combinatorics Difficulty 5.7 AIME, harder Prove it Ireland

Given an 8×88 \times 8 chess board, in how many ways can we select 5656 squares on the board while satisfying both of the following requirements:
1. All black squares are selected.
2. Exactly seven squares are selected in each column and in each row.

Solution

Switching the definition of selection and non-selection, we see that an equivalent formulation is to select eight squares, with one in each row and in each column, and no black squares selected. We assume that the non-black squares are white.

Orient the chessboard so that the square in row 11, column 11 is white. Let aia_i be the column of the selected white square in row ii, so iaii \mapsto a_i is a permutation of {1,,8}\{1, \dots, 8\} and aia_i has the same parity as ii. There are 44 choices for a1a_1 (a1{1,3,5,7}a_1 \in \{1, 3, 5, 7\}), then 33 for a3a_3 (a3{1,3,5,7}{a1}a_3 \in \{1, 3, 5, 7\} \setminus \{a_1\}), 22 for a5a_5, and 11 for a7a_7. After these selections, we again have 44 choices for a2a_2, 33 for a4a_4, etc. All of these sets of choices are independent of each other, so in all we have (4!)2=576(4!)^2 = 576 ways of performing our selection.

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.