Consider a simplified game of battleship. We are given a $4\times 4$ board on which we can place $2$ pieces. One destroyer which is a $1 \times 2$ squares and a submarine that is $1 \times 3$ squares. The pieces are placed on the board and cannot overlap, and are placed either vertically or horizontally.

Your opponent picks $8$ (of the $16$ squares) uniformly at random and then "shoots" at these $8$ squares. A ship is "sunk" if all the squares were the ship was were "shot".

What is the probability that both of the ships are sunk?

This is what I was told the answer is:

$$\frac{11 \choose 3}{16 \choose 8}$$

Since the solutions don't have an explanation this is what I think is the correct explanation, with the answer they gave (if you know the actual/correct answer, please explain it to me):

${16 \choose 8}$ are the total number of ways that the opponent can pick where to shoot bombs. Therefore the total number of outcomes (that we could choose) that we are considering is ${16 \choose 8}$.

That part makes sense to me. However, what doesn't make $100\%$ sense to me is how to get the numerator for our probability.

Given a fixed location where my ships are, then there are $5$ blocks that I have chosen. This can be interpreted that I have "fixed" a set of $5$ numbers (the location of the ships) and I am choosing from it. Therefore, from this set of $5$ numbers, the number of ways to sink the ships are:

First the opponent chooses the five correct location of the ships: $5 \choose 5$

Second, then the opponent chooses the remaining $3$ numbers on the board (since we already choose $5$ and we have to bomb $3$ places, the remaining number of time we can choose is $3$). However, we choose from the remaining $16-5 = 11$ remaining places leading to: $11 \choose 3$

Which is what the answer seem to suggest... However, I do not think this analysis is $100\%$ correct.

This is the reason:

This analysis only holds if I fixed a location for the ships. However, the question asks for the probability that both ships are sunk. For me that event should consider all possible places where the ships could be placed, which the answer that I explained doesn't incorporate. Since the question restricts how to place ships, because a destroyer has to have its whole body connected and hence its pieces next to each other, then it complicates how to count.

With this extension (different interpretation of the question), what would the probability be?

It feels to me that its the above probability, times the number of ways we can place the ships with the restriction that we can just "split the ships". What do people think?

Also, is my second interpretation of the question meaningful? Maybe there is a reason this interpretation wasn't used, maybe it leads to a problem that doesn't make sense? Not sure...

Also, it seems to me that I might be confused in the difference between the conditional and unconditional event in question, if they have the same probability could you please explain? I obviously would have not written my above explanation if I knew that the two event were actually the same. Please clarify this last point, since it seems to be the whole reason that this question even exists.

  • $\begingroup$ @DonLarynx what do you mean? I am just trying to understand this, how else am I suppose to understand it? $\endgroup$ – Charlie Parker Dec 22 '14 at 20:04
  • $\begingroup$ Also, the probability that both ships were sunk is the probability that one ship was sunk plus the probability that the other ship was sunk. $\endgroup$ – Don Larynx Dec 22 '14 at 20:04
  • $\begingroup$ hahahahaha thanks. @jameselmore $\endgroup$ – Charlie Parker Dec 25 '14 at 21:09

You put the ships in some $5$ squares on the board. The conditional probability that the ships are sunk, given your choice, is the probability that the opponent chooses those $5$ squares plus any $3$ other squares, and that is ${11 \choose 3}/{16 \choose 8}$. Since this is the same no matter which choice you make, it is also the (unconditional) probability that your ships will be sunk.

EDIT: Now a different (and maybe more interesting) question is whether the opponent has a better strategy than a random choice of the $8$ squares. The answer is certainly yes, because many of her random choices involve wasted shots that can't possibly contribute to sinking both ships. For example, it's clearly wasteful to shoot at a square without shooting at any of its neighbours.

  • $\begingroup$ I think I understand it if the ships have a fixed selection. However, it is not clear to me why the conditional and unconditional probs should be the same. I think that is the whole reason this question even exists. Do you mind clarifying that to me? $\endgroup$ – Charlie Parker Dec 22 '14 at 20:12
  • 1
    $\begingroup$ Let's denote your choice as $X$, and let $A$ be the event that your ships are sunk. We have $\mathbb P(A | X = x) = c$ for all possible $x$. Then $$\mathbb P(A) = \sum_{x} \mathbb P(A | X = x) \mathbb P(X = x) = c \sum_{x} \mathbb P(X=x) = c$$ $\endgroup$ – Robert Israel Dec 22 '14 at 20:18
  • $\begingroup$ See e.g. en.wikipedia.org/wiki/Law_of_total_probability $\endgroup$ – Robert Israel Dec 22 '14 at 20:19
  • $\begingroup$ basically you are saying that the probability that your ships are sunk is independent of where you placed them? (because the opponent can't see where you placed them...?) $\endgroup$ – Charlie Parker Dec 22 '14 at 20:25
  • 1
    $\begingroup$ Yes, if the opponent uses this strategy of choosing $8$ squares at random, the probability that your ships are sunk is independent of where you placed them. $\endgroup$ – Robert Israel Dec 22 '14 at 20:55

Suppose the ships could be broken up into individual squares, so you have 11 possible squares you could hit and still miss the ships. However, you only have eight shots, so you can only have $11!/(8!*3!)$ possible ways. There is a number $11 \choose 3$ ways that this happens.

Surprisingly, the answer is still the same if the ships CAN'T be broken up. (Why?)

  • $\begingroup$ I dunno why thats my question! :p (I didn't down vote your answer btw). $\endgroup$ – Charlie Parker Dec 22 '14 at 20:21
  • $\begingroup$ It's because the number of squares that are available to hit (and miss) remains the same, regardless of how they are connected :) $\endgroup$ – Don Larynx Dec 22 '14 at 20:23
  • $\begingroup$ @CharlieParker: Also, the squares are indistinguishable, so the order does not matter - hence why we use a combination instead of a permutation. If every square was colored differently, the 8! would not be in the divisor. $\endgroup$ – Don Larynx Dec 22 '14 at 20:43

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.