Olympiad Maths Prep

Track / Stage 3 / 54 of 260 #54 of 2000

Problem 54

AMC 10/12, early questions
Combinatorics Difficulty 3.1 Find the answer

A set of 2525 square blocks is arranged into a 5×55 \times 5 square. How many different combinations of 33 blocks can be selected from that set so that no two are in the same row or column?
(A) 100(B) 125(C) 600(D) 2300(E) 3600\textbf{(A) } 100 \qquad\textbf{(B) } 125 \qquad\textbf{(C) } 600 \qquad\textbf{(D) } 2300 \qquad\textbf{(E) } 3600

Official solution

There are 2525 ways to choose the first square. The four remaining squares in its row and column and the square you chose exclude nine squares from being chosen next time.
There are 1616 remaining blocks to be chosen for the second square. The three remaining spaces in its row and column and the square you chose must be excluded from being chosen next time.
Finally, the last square has 99 remaining choices.
The number of ways to choose 33 squares is 25⋅16⋅9,25 \cdot 16 \cdot 9, but the order in which you chose the squares does not matter as the blocks are indistinguishable, so we divide by 3!3!.
25⋅16⋅93⋅2⋅1=25⋅8⋅3=100⋅6=(C) 600\frac{25 \cdot 16 \cdot 9}{3 \cdot 2 \cdot 1} = 25 \cdot 8 \cdot 3 = 100 \cdot 6 = \boxed{\mathrm{(C) \ } 600}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.