Bomb The Target! Part 2

The problem can be modelled as a $3$ -states Markov chain . Let it be:

$\displaystyle M=\{\text{bomb misses the target}\} \\ H1=\{\text{bomb hits the target one time}\} \\ H2=\{\text{bomb hits the target two consecutive times}\}$

So, we have

$\displaystyle \textbf{P}=\begin{array}{c}\ M & H1 & H2 & \\ \frac{1}{2} & \frac{1}{2} & 0 & M \\ \frac{1}{2} & 0 & \frac{1}{2} & H1 \\ 0 & 0 & 1 & H2 \end{array}$

The initial state is

$\displaystyle \textbf{u}=\bigg(\frac{1}{2}, \frac{1}{2}, 0\bigg)$

Hence the probability that the city is not destroyed after $7$ drops is

$\displaystyle \mathbb{P}(\text{the city is not destroyed after 7 drops})=1-\{\textbf{u} \cdot \textbf{P}^6\}_3=\frac{17}{64}=\frac{a}{b} \\ a+b=\boxed{81}$

Let the bomb that failed be represented by N and the other one represented by Y. We need to count how many 7-character words with only the letters Y and N and no consecutive Y (the total number of words without that restriction is 2^7 = 128).

Be Y(n) the number of n-character words with at least 2 consecutive Y, Ny(n) the number of n-character words with no consecutive Y ending with Y and Nn(n) the number of n-character words with no consecutive Y ending with N.

We can see that:

Y(n+1) = 2×Y(n) + Ny(n)

Ny(n+1) = Nn(n)

Nn(n+1) = Nn(n) + Ny(n)

With that you can find the closed formulas or just complete a table knowing that Y(2) = 1, Ny(2) = 1 and Nn(2) = 2:

Y Ny Nn

1 1 2

3 2 3

8 3 5

19 5 8

43 8 13

94 13 21

We want (13+21)/128 = 17/64.

By curiosity, if F(1) = 1, F(2) = 1 and F(n) = F(n-1) + F(n-2), I got:

Ny(n) = F(n)

Nn(n) = F(n+1)

Y(n) = 2^n - F(n+2)

It's not exactly a closed formula, but you can use Fibonacci's closed formula!

Use casework:

Denote M as a miss and H as a hit.

---

First consider the first case: The bomb misses the town 7 times.

MMMMMMM

This gives 1.

---

Second: The bomb hits the town once and misses 6 times.

MMMMMMH

There are 7C6 ways or 7 ways to arrange these.

---

Third: The bomb hits 2 times and misses 5 times.

MMMMMHH

There are 7C5 ways or 21 ways to arrange with no restrictions.

However, we must notice that there can be two hits in a row which will destroy the town, and there are six ways this can happen.

Therefore 7C5 - 6 = 15 for this case.

---

Fourth: The bomb hits 3 times and misses 4 times

MMMMHHH

Divide this into 3 subcases:

---

4a: First we have two H's on the sidelines like so:

HM_ _ _MH

The places next to the hits must be misses or else the town is gone, so we have 3 choices for the final H.

---

4b: We have one H on the sideline.

HM_ _ _ _M

The reason we have a miss on the other side is because we cannot have a H because that would interfere with our 4a case(Try to see how!).

Now there are 4C2 ways to place the final H's, however there are three ways they could be together and so 4C2 - 3 = 3.

Multiply by 2 because the H could be on the other side.

---

4c: We have no H's on the sidelines

M _ _ _ _ _M

Now notice there is only one configuration that satisfies this:

MH_ H _H M

So that gets 1

Adding up 4a, 4b, 4c we get 10.

---

Fifth: The bomb hits 4 times and misses 3 times:

Notice only one configuration satisfies this:

HMHMHMH

So that gets 1

Adding up all the cases we get 34.

---

Ans. 34/128 or 17/64