Mind your rows and columns .....

On a standard 8 8 by 8 8 chessboard, k k pawns are randomly placed in different squares, (with 1 k 64 1 \le k \le 64 ). Let p ( k ) p(k) be the probability that, with k 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 ) = a b p(3) + p(4) + p(5) + p(6) = \dfrac{a}{b} , where a a and b b are positive coprime integers, then find b a b - a .


The answer is 102559.

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.

1 solution

For 3 k 6 3 \le k \le 6 choose k k rows in ( 8 k ) \binom{8}{k} ways and k k columns in ( 8 k ) \binom{8}{k} ways. The squares where these k k rows and k k columns intersect are where we can put the k k pawns. In the first column from the left, choose one of the rows in one of k k ways. In the next column to the right, choose one of the rows in one of k 1 k - 1 ways. Repeat this process through to the k k th chosen column, for which there will be just 1 1 row to choose from.

There are then k ! ( 8 k ) 2 k! * \dbinom{8}{k}^{2} ways of placing the k k pawns so that no two pawns lie in the same row or column as each other.

Without restrictions, there are ( 64 k ) \dbinom{64}{k} ways of placing k k pawns on the board. Thus

p ( k ) = k ! ( 8 k ) 2 ( 64 k ) p(k) = \dfrac{k! * \dbinom{8}{k}^{2}}{\dbinom{64}{k}} .

Using this formula we find that p ( 3 ) + p ( 4 ) + p ( 5 ) + p ( 6 ) = 232148 334707 p(3) + p(4) + p(5) + p(6) = \dfrac{232148}{334707} .

This gives us a = 232148 , b = 334707 a = 232148, b = 334707 and b a = 102559 b - a = \boxed{102559} .

Nice interpretation.

The "direct" way of calculating (say) p ( 3 ) 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 49 × 36 63 × 62 \frac{ 49 \times 36 } { 63 \times 62 } . This agrees with the formula that you calculated.

Calvin Lin Staff - 6 years, 9 months ago

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 k . So for an m m by n n grid of squares, with 1 k min ( m , n ) 1 \le k \le \min(m,n) , we would have

p ( k ) = k ! ( m k ) ( n k ) ( m n k ) = m ! n ! ( m n ) ! ( m n k ) ! ( m k ) ! ( n k ) ! p(k) = \dfrac{k! * \dbinom{m}{k} \dbinom{n}{k}}{\dbinom{mn}{k}} = \dfrac{m! * n!}{(mn)!} * \dfrac{(mn - k)!}{(m - k)! * (n - k)!} .

Brian Charlesworth - 6 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...