Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 UNCO Math Contest II Problems/Problem 5"

(→‎Solution)
(→‎Solution)
 
Line 19: Line 19:
  
 
== Solution ==
 
== Solution ==
−
(a) <math>\tfrac{6}{455}</math>  
+
This problem is equivalent to asking how many ways rooks can be placed on a <math>n \times n</math> 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 <math>n</math> columns. The second is placed in next row and has <math>n-1</math> columns. We go on until last rook has only <math>1</math> place. Thus, total ways to place is <math>n!</math>. Total possible ways to place is <math>\binom{n^2}{n}</math> since we have <math>n^2</math> squares, and we have <math>n</math> rooks/coins.
  
−
(b) <math>\frac{n!}{\binom{n^2}{n}}</math>
+
Probability is <math>\boxed{\frac{n!}{\binom{n^2}{n}}}</math>
 +
 
 +
For <math>(a)</math>, we have <math>n=4 \implies \boxed{P =\tfrac{6}{455}}</math>
 +
 
 +
=== Note ===
 +
In general, for <math>r</math> rows and <math>s</math> columns, we have <math>min(r,s)</math> ways to place rooks such that no two attack each other, and a total of <math>\frac{(max(r,s))!}{[max(r,s) - min(r,s)]!}</math> ways to place these rooks on the board. The result can be derived easily by the same method that was used in this solution.
  
 
== See also ==
 
== See also ==

Latest revision as of 07:13, 29 August 2025

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.

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_UNCO_Math_Contest_II_Problems/Problem_5&oldid=259150"