2010 UNCO Math Contest II Problems/Problem 5

Problem

(a) In the $4 \times 4$ grid shown, four coins are randomly placed in different squares. What is the probability that no two coins lie in the same row or column?

$\begin{tabular}{|c|c|c|c|} \hline &&& \\ \hline &&& \\ \hline &&& \\ \hline &&& \\ \hline \end{tabular}$

(b) Generalize this to an $N \times N$ grid.

Solution

This problem is equivalent to asking how many ways rooks can be placed on a $n \times n$ chessboard such that no two rooks attack each other. Let us go down row-by-row and permute over the columns (as number of rows and columns are equal).The first rook can be placed in any of the $n$ columns. The second is placed in next row and has $n-1$ columns. We go on until last rook has only $1$ place. Thus, total ways to place is $n!$ . Total possible ways to place is $\binom{n^2}{n}$ since we have $n^2$ squares, and we have $n$ rooks/coins.

Probability is $\boxed{\frac{n!}{\binom{n^2}{n}}}$

For $(a)$ , we have $n=4 \implies \boxed{P =\tfrac{6}{455}}$

Note

In general, for $r$ rows and $s$ columns, we have $min(r,s)$ ways to place rooks such that no two attack each other, and a total of $\frac{(max(r,s))!}{[max(r,s) - min(r,s)]!}$ ways to place these rooks on the board. The result can be derived easily by the same method that was used in this solution.

2010 UNCO Math Contest II (Problems • Answer Key • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10
All UNCO Math Contest Problems and Solutions

Page

Toolbox

Search

2010 UNCO Math Contest II Problems/Problem 5

Contents

Problem

Solution

Note

See also