0
$\begingroup$

If we start with a $2\times 30$ chessboard and we remove $15$ black squares, how can I find the probability that we get $7$ white squares which don't have any neighbours? (A white square will have no neighbours if all of the black squares adjoining it are removed).

$\endgroup$
  • $\begingroup$ I assume that the black squares are selected uniformly, but are you looking for the probability that at least 7 white squares are isolated, or that exactly 7 white squares are isolated? $\endgroup$ – Peter Taylor Jun 12 '13 at 9:19
  • $\begingroup$ Excactly 7 white squares are isolated.... $\endgroup$ – user82063 Jun 12 '13 at 9:31
  • $\begingroup$ I would start with a smaller problem. Solving it might give you an idea of how to solve the original, or give you a feel for how hard the original is. $\endgroup$ – Gerry Myerson Jun 12 '13 at 9:40
0
$\begingroup$

If we label the columns where we delete the black square with an x and the ones where we don't with a . then we get a 30-character string containing 15 x and 15 .

Prepend and postpend x to handle the boundary cases (so that the end white squares are isolated respectively by a leading and trailing xxx)

Then each maximal non-overlapping substring of the form x$^{2+n}$ corresponds to $n$ isolated white squares.

Possible continuations:

  1. Partitions of 7. There are 15 partitions of 7, of which 4 would require more than 15 deleted squares (e.g. $7 = 1 + 1 + 1 + 2 + 2$ requires three runs of three and two runs of four, for a total of 17 deleted squares), so that leaves 11 cases to handle. They might be grouped with some thought.
  2. Create a recurrence in terms of the length of the board, the number of squares to delete, and the number of white squares to isolate.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.