Can I Cross? Let Me Flip a Coin.

Let's face it, I'm an addict of these riddles.

This week's riddle from Ollie at FiveThirtyEight is a longer one:

You’re on the north shore of a river, and want to cross to the south, via a series of 13 bridges and six islands, which you can see in the diagram below. But, as you approach the water, night falls, a bad storm rolls in, and you’re forced to wait until morning to try to cross. Overnight, the storm could render some of the bridges unusable — it has a 50 percent chance of knocking out each of the bridges. (The chance is independent for each bridge.)

 Question 1: What’s the probability you will be able to cross the river in the morning? (You have no boat, can’t swim, can’t fix the bridges, etc. No tricks.)

Now imagine a different, wider river, with many more islands — in fact, arbitrarily many. Specifically, imagine that the islands are arrayed in an N-rows-by-N+1-columns grid — similar to before, where N happened to equal two — and connected by bridges to each adjacent island in the same way. Each island adjacent to the shore is also connected by a bridge to the shore. It would look something like this:

 Question 2: What’s the probability you’ll be able to cross this river in the morning, after the same storm — with the same independent 50 percent chance of knocking out each bridge — rolls through?

There is also some Extra Credit, but I'm skipping that.

So, first we'll deal with Question 1.  I wondered for a while what was special about the N x N+1 pattern, but it became clear rather quickly.

We would like to solve for p, the probability that we will make it across the river.  There is also q = 1-p which is the probability that we do not make it across the river.

To solve this let's first imagine that all of these bridges are low enough that motor boats cannot go underneath them.  Motorboat Billy has been really pissed about this whole island and bridge system for a very long while now because every time he wants to go from the East River to the West River, he has to go through the long painstaking process of dragging his boat ashore and pulling it all the way beyond this pesky bridge system.

Needless to say, he is excited about this storm.  He will finally have some probability that the storm will take away enough bridges that he will get to pass!

Notice that the potential places he can pass are lined up exactly like the bridges.  This would not be the case if it were not N x N+1.

We are looking at the same exact problem!  What does this mean?  The probability that Motorboat Billy will be able to pass from the East River to the West River is q, the probability that we will not be able to pass from the North to the South shore, and the probability that he will not be able to pass is p, the probability that we will get to pass.

Since both problems are equivalent, p=q, and q=p, and the only way that this can happen is if p=q=0.5.

Hence, the probability is 50%.  You can add as many islands and bridges as you want. As long as it remains in the N x N+1 pattern, the probability will remain 50%.

How do you like them apples?