On a standard 8 by 8 chessboard, k pawns are randomly placed in different squares, (with 1 ≤ k ≤ 6 4 ). Let p ( k ) be the probability that, with k pawns being so placed, no two pawns lie in the same row or column as each other.
If p ( 3 ) + p ( 4 ) + p ( 5 ) + p ( 6 ) = b a , where a and b are positive coprime integers, then find b − a .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice interpretation.
The "direct" way of calculating (say)
p
(
3
)
is that
- The first pawn can be placed anywhere.
- The second pawn can be placed in 49 of the remaining 63 squares.
- The third pawn can be placed in 36 of the remaining 62 squares.
Hence, the probability is 6 3 × 6 2 4 9 × 3 6 . This agrees with the formula that you calculated.
Log in to reply
Thanks. Yes, the 'direct' way works well, but I thought it would be best to develop a general formula that could then be adapted for larger grids and hence larger values of k . So for an m by n grid of squares, with 1 ≤ k ≤ min ( m , n ) , we would have
p ( k ) = ( k m n ) k ! ∗ ( k m ) ( k n ) = ( m n ) ! m ! ∗ n ! ∗ ( m − k ) ! ∗ ( n − k ) ! ( m n − k ) ! .
Problem Loading...
Note Loading...
Set Loading...
For 3 ≤ k ≤ 6 choose k rows in ( k 8 ) ways and k columns in ( k 8 ) ways. The squares where these k rows and k columns intersect are where we can put the k pawns. In the first column from the left, choose one of the rows in one of k ways. In the next column to the right, choose one of the rows in one of k − 1 ways. Repeat this process through to the k th chosen column, for which there will be just 1 row to choose from.
There are then k ! ∗ ( k 8 ) 2 ways of placing the k pawns so that no two pawns lie in the same row or column as each other.
Without restrictions, there are ( k 6 4 ) ways of placing k pawns on the board. Thus
p ( k ) = ( k 6 4 ) k ! ∗ ( k 8 ) 2 .
Using this formula we find that p ( 3 ) + p ( 4 ) + p ( 5 ) + p ( 6 ) = 3 3 4 7 0 7 2 3 2 1 4 8 .
This gives us a = 2 3 2 1 4 8 , b = 3 3 4 7 0 7 and b − a = 1 0 2 5 5 9 .