No black neighbors

We can use linearity of expectation to break up the problem so we only have to consider the probabilities of each white square having its neighbors removed.

The probability a corner square has both of its neighbors removed is $\frac {30}{60}) \times (\frac {29}{59}$ .

The probability an edge square has all three of its neighbors removed is $\frac {30}{60}) \times (\frac {29}{59}) \times (\frac {28}{58}$ .

Hence the expected number of white squares with no neighbors is $2 \times (\frac {30}{60}) \times (\frac {29}{59}) + 58 \times (\frac {30}{60}) \times (\frac {29}{59}) \times (\frac {28}{58}) = \frac {435}{59}$ .

Hence , $a + b = 435 + 59 = 494$ . Thanks.

Suppose we have a corner white square. Since it has two black neighbours, the probability that both are taken is $\frac {C(58, 28)}{C(60,30)}$ . For a non-corner white square, it has three black neighbours, so the probability that all are taken is $\frac {C(57, 27)}{C(60, 30)}$ .

Thus, the expected number of white squares without any neighbours is:

$2\times \frac {C(58, 28)}{C(60,30)} + 58\times \frac {C(57, 27)}{C(60, 30)} = \frac{435}{59}$

[ Tip : here's a quick reason why this works. Imagine a set of N = C(60, 30) elements, comprising of all possible ways to remove 30 black squares from 60. We wish to count the overall number of white squares without neighbours then divide by N. For that, we can just focus on each white square and count the number of configurations where it has no neighbours left. ]

Let F(x) and E(x) be the probability that a white square will have no neighbors after removing 30 black squares and the expected number of white squares that have no neighbors respectively.

E(x) = summation of (x k)*F(x k) from k=1 to k=n.

Linearity of Expectation is the best way to use to solve this problem. Linearity of Expectation basically says that the expected value of a sum of random variables is equal to the sum of the individual expectations.

We will consider two probabilities: 1. The probability that a white corner square has both of its neighbors removed. 2. The probability that a white edge square has all of its three neighbors removed.

The probability of 1. is given by:

(30/60)*(29/59) = 29/118

The probability of 2. is given by

(30/60) (29/59) (28/58) = 7/59

Thus, the expected number of white squares is given by:

E(x) = 2 (29/118) + 58 (7/59) = 435/59

The desired sum a+b follows: 435+59 = 494

I tried to use the formatting guide but the moment I preview it, the desired term doesn't appear. I'm very sorry.

Main idea : Use linearity of expected value , compute the probability that each square has no black neighbor, and sum them up.

Complete proof :

Let "to be cut off" mean "to have no neighbors".

First, by linearity of expected value, the value we seek for is equal to the sum of the expected numbers of each white square being cut off. Also note that the expected number of a white square being cut off is essentially the probability of it being cut off.

There are $2$ white squares with two black neighbors (at the corners of the board) and $58$ white squares with three black neighbors (everywhere else).

The probability that a white square having two black neighbors is cut off is equal to the probability that both black squares are chosen to be removed, which means $\frac{30}{60} \cdot \frac{29}{59}$ (there are $30$ removed black squares among $60$ , and after removing one, there are $29$ more squares to be removed among $59$ ). Similarly, the probability that a white square having three black neighbors is cut off is equal to $\frac{30}{60} \cdot \frac{29}{59} \cdot \frac{28}{58}$ .

So, the expected number of black squares removed is:

$2 \cdot \left( \dfrac{30}{60} \cdot \dfrac{29}{59} \right) + 58 \cdot \left( \dfrac{30}{60} \cdot \dfrac{29}{59} \cdot \dfrac{28}{58} \right)$

$= \left( \dfrac{30}{60} \cdot \dfrac{29}{59} \right) \left(2 + 58 \cdot \dfrac{28}{58} \right)$

$= \dfrac{29}{118} \cdot 30$

$= \dfrac{435}{59}$

So $a = 435, b = 59$ , and so $a+b = \boxed{494}$ .

Motivation : The motivation is pretty clear if you know linearity of expected value. After that, it's just simple bashing of probabilities.

Generalization : Replace $60$ with $2n$ , and you can proceed similarly to obtain the expression $2 \cdot \left( \frac{n}{2n} \cdot \frac{n-1}{2n-1} \right) + (2n-2) \cdot \left( \frac{n}{2n} \cdot \frac{n-1}{2n-1} \cdot \frac{n-2}{2n-2} \right) = \frac{n(n-1)}{2(2n-1)}$ .

Suppose that the black and white squares in the $j$ th column are labelled $B_j$ and $W_j$ respectively, for $1 \le j \le 60$ . Let $N_j$ be the random variable $N_j \; = \; \left\{ \begin{array}{lcl} 1 & \qquad & W_j \mbox{ has no neighbours after the process} \\ 0 & \qquad & otherwise \end{array} \right.$ and let $N = N_1 + N_2 + \cdots + N_{60}$ be the number of white squares with no neighbours after the process. Now $\begin{array}{rcl} \mathbb{E}[N_1] & = & \mathbb{P}[N_1=1] \; = \; \mathbb{P}[B_1,B_2 \mbox{ taken}] \\ & = & {58 \choose 28} {60 \choose 30}^{-1} \; = \; \frac{29}{118} \\ \mathbb{E}[N_2] & = & \mathbb{P}[N_2=1] \; = \; \mathbb{P}[B_1,B_2,B_3 \mbox{ all taken}] \\ & = & {57 \choose 27}{60 \choose 30}^{-1} \; = \; \frac{7}{59} \end{array}$ Indeed it is clear that $\mathbb{E}[N_j] \; = \; \left\{ \begin{array}{lcl} \mathbb{E}[N_1] \; = \; \tfrac{29}{118} & \qquad & j = 1,60 \\ \mathbb{E}[N_2] \; = \; \tfrac{7}{59} & \qquad & 2 \le j \le 59 \end{array} \right.$ and hence $\begin{array}{rcl} \mathbb{E}[N] & = & \mathbb{E}[N_1] + \mathbb{E}[N_2] + \cdots + \mathbb{E}[N_{60}] \\ & = & 2\times\tfrac{29}{118} + 58\times\tfrac{7}{59} \; = \; \tfrac{435}{59} \end{array}$ giving the final answer $435 + 59 = 494$ .

This use of the so-called indicator functions $N_1,N_2,\ldots,N_{60}$ - events which are equal to $1$ when something happens, and $0$ otherwise, and adding them up to count the number of times that that thing happens - is a really useful mathematical device. We only need to look at one indicator event at a time when calculating the expectation of the sum, and that means we can avoid all sorts of unpleasant considerations concerning the lack of independence of the various events.

Instead of thinking in terms of neighbouring squares, I found it easier to think in terms of sequences of $0, 1$ .

If we let $0$ mean a black square which is not removed, and $1$ mean a black square which is removed, and we list the black squares from left to right, then the problem becomes:

"In a sequence of 60 digits, including 30 $1$ 's, what is the expected number of $111$ triples; or $11$ at the start or end" . Those conditions correspond to white squares with no neighbours.

Since we are counting the expected value, we can do this by considering all possible combinations of digits, and then adding up the total number of cases which match the conditions we are looking for.

I'll do this more generally: for $n$ total digits of which $m$ are $1$ . The total number of possible positions is of course $\binom{n}{m}$ .

If we consider positions starting $11$ , then there are $n-2$ places remaining, and $m-2$ possible $1$ 's to fill in. So there are $\binom{n-2}{m-2}$ total occurrences of this; and similarly for final $11$ .

For $111$ , there are $n-2$ locations it can be found in the string; and then for each of those locations , there are $n-3$ remaining digits of which $m-3$ are 1, for a total of $\binom{n-3}{m-3}$ .

Totalling this all up, $\begin{aligned} E &= {1 \over \binom{n}{m}} [2\binom{n-2}{m-2} + (n-2)\binom{n-3}{m-3}] \\ &= {{m!(n-m)!} \over n!} [2 {{(n-2)} \over {(m-2)(n-m)}} + (n-2) \frac{n-3}{(m-3)(n-m)}] \\ &= {{m!(n-m)!} \over n!} (2 + (m-2)) \frac{n-2}{(m-2)(n-m)} \\ &= \frac{m^2(m-1)}{n(n-1)} \end{aligned}$

Filling in $n=60, m=30$ gives $E = \frac{29 \cdot 15}{59} = \boxed{\frac{435}{59}}$

probability that one square adjacent to corner white square =1/2 .
probability that other square adjacent to corner white square =29/59 .
since there are two corner squares probability that corner squares are neighborless =2(1/2 * 29/59) = 29/59 .
similarly for other squares=58(1/2 29/59 *28/58) = 29/59 14 .
adding = 435/59. thus answer = 435 +59=494