Removing squares from a chessboard

Each piece of the chessboard must contain at least one white square. We will count the expected number of white squares sharing a corner of the chessboard that become separated by the deletion of the black squares. The expected number of pieces of the chessboard will be one more than this number.

We will solve the problem more generally, for a $2 \times n$ board and $m$ pieces. We assign values of $1, 2, \ldots, n$ the columns of the board. Let $X_i$ be an indicator variable which has value $1$ if the white square in column $i$ becomes separated from the white square in column $i + 1$ . Then by linearity of expectation, the expected number of pieces the board is divided into is $1 + \sum\limits_{i=1}^{n-1} E[X_i]$ . It is easy to see that $E[X_i]$ is $\frac{k(k-1)}{n(n-1)}$ for each value of $i$ , since we require two specific black squares to be deleted. Thus, the expected number of pieces is $1 + (n-1) \frac{k(k-1)}{n(n-1)} = 1 + \frac{k(k-1)}{n}.$ Since we want at least $m$ pieces, we have $1 + \frac{k(k-1)}{n} \geq m,$ which we can simplify to $k^2 - k - n(m-1) \geq 0.$ We can solve this using the quadratic formula to get $k \geq \frac{1}{2} + \sqrt{\frac{1}{4} + n(m-1)}.$

Substituting in $n = 500, m = 20$ gives $k = 98$ as the minimum possible value.