21
$\begingroup$

You are on the North Shore of a river, and you want to get to the South Shore. In the river are 6 islands and 13 bridges connecting the islands and shores. However, a storm gives a 50% chance to each bridge to collapse before you cross (independent of each other).

Some bridges are now collapsed (or they could be all intact or all collapsed). What is the probability that you will be able to make it over the river?

From FiveThirtyEight.

$\endgroup$
  • $\begingroup$ good math question. $\endgroup$ – Oray Aug 30 '17 at 20:44
  • $\begingroup$ Very similar (not sure if similar enough for duplicate) to puzzling.stackexchange.com/questions/28119/… $\endgroup$ – StephenTG Aug 31 '17 at 3:40
  • $\begingroup$ It sounds like the wording is that each bridge has a 50% chance to collapse right before you cross it. As in, you put one foot on the bridge and either it holds or doesn't, so you won't know which bridges are safe until you start. Which could mean you might need to double back, upon which the bridge you previously crossed might now collapse. That's a much trickier problem. $\endgroup$ – user3294068 Feb 6 '18 at 20:17
29
$\begingroup$

The answer is

exactly 50%.

To see this,

Suppose in a parallel universe, someone wants to cross from the West Shore to the East Shore at the same you're trying to cross from North to South:

enter image description here

Instead of saying the bridges are destroyed, we'll say that for each bridge, either the orange bridge or the green bridge that crosses it are built. This doesn't change the probability that the North-South crossing is possible.

In this situation, clearly exactly one of you or your imaginary friend will be able to cross -- if a West-East crossing is impossible, this means West and East are separated by a path that goes from North to South, and vice-versa. Because the situation is completely symmetric, the chance that you will be the one to cross, and not the one in the parallel universe, is 50%.

$\endgroup$
  • 3
    $\begingroup$ Probably the best 'visual' solution to a problem that I have ever seen. $\endgroup$ – Penguino Aug 30 '17 at 21:41
  • $\begingroup$ Very nice solution! Just a thought - How do we go about solving it if the probability of bridge breaking is not 0.5? $\endgroup$ – glugglug Aug 31 '17 at 8:02
  • $\begingroup$ Have seen this in www.brilliant.org. According to the people there, if the bridges are not that way, or the probability is not that good, then it's difficult to count. $\endgroup$ – William Nathanael Aug 31 '17 at 10:24
3
$\begingroup$

There is of course, a brute force way to answer this problem if, as @glugglug asked, the probability of a bridge breaking is not 0.5.

First, what's the probability of the three eastmost bridges all still standing? This gives us a path from North to South using only three bridges. Well, if the probability of a bridge still standing is p (in our case, p=0.5), the probability of all three of those bridges standing is p^3 (in this specific case, 0.125).

If those bridges are up, great, we will take those, but in the remaining 0.875 cases (1-p^3), what are the chances that the three center bridges are standing? Again, that's p^3, but it's p^3 out of the remaining 1-p^3 cases, not out of 1, because we wouldn't be looking at the center bridges if we had already found a way across on the eastmost ones. So, the chances of either being able to cross the eastmost briges or the center bridges are (p^3) + (p^3) * (1 - p^3).

Or, more generally, (probability of all the previous routes) + (probability of current route)*(1 - probability of all the previous routes).

For the westmost bridges, we would do the same thing, the probability of those three bridges standing is p^3, the total probability of a route using only three bridges existing is
[(p^3) + (p^3) * (1 - p^3)] + (p^3) * [(p^3) + (p^3)*(1 - p^3)].

You have to continue summing these up until you have accounted for all possible routes, I believe there are 3 that only use 3 bridges (each with probability p^3), 8 that use 4 bridges (p^4), 4 that use 5 bridges (p^5), 4 that use 6 bridges (p^6), and 4 that use 7 bridges (p^7), but I just did that very quickly in my head and may have missed some.

If anyone wants to do all that out by hand with p=0.5 and see if the answer is also 0.5, be my guest, I may do it later if I'm bored enough.

$\endgroup$
  • $\begingroup$ Not sure if this works as is, e.g if you have already determined that the path given by the three easternmost bridges is not possible, then a 4-bridge path that begins using two eastern bridges has a probability smaller than p^4 of being available. $\endgroup$ – ffao Sep 1 '17 at 20:28
  • $\begingroup$ @ffao you might be right, but this is still more accurate than my first-instinct guess, which was the probability of a 3 bridge path existing was 3/8ths, since the probability of one of those paths existing was 1/8th and I added all of those together... whoops $\endgroup$ – MMAdams Sep 1 '17 at 20:36
  • 4
    $\begingroup$ If $p$ is the probability that a bridge is intact, and $q=1-p$, then the probability of being able to cross is $$p^{13}+13p^{12}q+78p^{11}q^2+283p^{10}q^3+677p^9q^4+1078p^8q^5+1089p^7q^6+627p^6q^7+209p^5q^8+38p^4q^9+3p^3q^{10}$$ I did this by computer by checking all $2^{13}$ cases. The coefficient of $p^kq^{13-k}$ is the number of those cases with $k$ intact bridges and $13-k$ broken bridges that still connects the two river banks. Note that the coefficients of $p^kq^{13-k}$ and $p^{13-k}q^k$ added together are $\binom{13}{k}$ due to that self-duality. $\endgroup$ – Jaap Scherphuis Sep 2 '17 at 0:53
  • $\begingroup$ Nice! Thought as much, needs a program. Thanks! $\endgroup$ – glugglug Sep 5 '17 at 6:41

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.