The Five Bridges Puzzle

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum

There are times when I feel like I’m in a big forest and don’t know where I’m going. But then somehow I come to the top of a hill and can see everything more clearly. When that happens, it’s really exciting.

Maryam Mirzakhani, 2005

A little over a year ago, I wrote here about the Seven Bridges of Königsberg puzzle and its mathematical history. Recently I was reminded of another bridge-related puzzle, which also has some interesting mathematics behind it

The image shows an arrangement of bridges, which can be used by the intrepid hero of the tale (pictured, top) to cross this river, via a pair of islands located in the center of the river. There are many ways to get from one side of the river to the other, and any subset of the five bridges might be used as part of such a crossing.

The set-up of the puzzle is as follows:

Last night, there was a ferocious storm in the area, which was sufficiently strong that it had a 50% chance of washing each of the five bridges completely away, so they’re impassable. Each bridge separately has a 50-50 chance of being destroyed, and our adventurer arrives at the river the following morning. Given the layout of bridges and islands, what is the probability that they’ll be able to find a route across?

If you’d like to take some time to go away and think about the puzzle, do so now.

Crossing that bridge when you come to it

There are several ways to approach this puzzle. You might begin by thinking about all the possible ways our brave explorer could get from one side of the river to the other. They could go down the left-hand side of the diagram, crossing to the left-hand island then over to the far side; they could do the same down the right-hand side; or they could cross the first bridge to an island, then move to the other island, then use the second bridge to finish the crossing, and there are two mirror-image variants on this route.

Since each bridge has a 50-50 chance of washing away, we can analyze each possible route across the river separately. For example, if the adventurer were to choose the route down the left-hand side of the diagram, crossing two bridges to get to the far bank, each of these has ½ chance of being intact, so the chances the route is passable can be calculated by p(top bridge is intact) × p(bottom bridge is intact) = ½ × ½ = ¼.

For the other two-bridge route, the same calculation applies, and for the three-bridge routes that involve crossing between the two islands, the probability is  ½ × ½ × ½ = ⅛. Since any one of these routes being passable would result in our hero being able to cross, we could find the probability by adding together all the options – ¼ + ¼ + ⅛ + ⅛, which gives a total of ¾ (75%) chance.

However, this naive approach has some issues. For example, the case where none of the bridges get washed away, which would be included in all of these possibilities, has been counted multiple times. This also applies to several other combinations that involve only one, or even two bridges being washed away. So the actual probability will be less than 75% – since including them all separately will give an overestimate.

The thorough way to check all these overlapping possibilities is to list all the possible combinations of intact and destroyed, for each of the five bridges. Since there are five things with two possibilities for each, we should have 2×2×2×2×2 = 25 = 32 combinations, which we could list.

L-R: no bridges are destroyed; top left bridge only; bottom left bridge only; top left and bottom left bridges destroyed, etc.

Once we’ve written out all 32 combinations, we can consider that each of them occurs with probability 1/32 (since each of them involves five things each being in one of two equally likely states, so they all have the same probability). Then, we simply need to count how many of them contain an intact route between the two banks.

Doing so results in a total of 16 of the 32 possibilities resulting in a successful crossing – which means the probability is ½.

While the earlier route-based method gave the wrong answer, it can also be adapted – by carefully removing any overlap in the cases you’re counting (given that the bridges you need to travel that route are intact, what is the state of the remaining bridges?) and this also results in the same answer.

The Puzzle With Five Bridges

While this might seem like a straightforward probability puzzle, with not much interest, I first encountered it in an interesting context – alongside a second, similar-looking puzzle.

This is the Puzzle With Five Bridges:

A slightly different fearless adventurer, who travels by boat, is attempting to sail along this river. However, the bridges crossing this river are built too low for the boat and its passenger to travel underneath. Luckily for our explorer, there’s been a ferocious storm in the area, which was sufficiently strong that it had a 50% chance of washing each of the five bridges completely away, making it passable by boat.

What are the chances that our boat-based explorer can successfully navigate from one end of this section of river to the other?

I imagine you’re not naive enough to imagine these two puzzles are unrelated, but if you’d like to take a minute to think about how this one works, please do so now.

Duplicate bridge

With a little thought, it’s possible to see that this puzzle works in exactly the same way – the river is passable only if the correct subset of the bridges has been washed away, which means we can list all the possibilities and count them – and in this case, again 16 of them result in the river being open, and the other 16 block the route.

These puzzles are very similar – and in fact, it’s worse than that. If we draw a diagram of the routes the boat can take (sections of river they’d sail along if the corresponding bridge were to have been washed away), it actually looks exactly the same as the network of bridges. The two networks look exactly the same, containing the same arrangement of points connected in the same way.

The other crucial point to note here is that the 16 cases in which the boat-based adventurer is successful are exactly those in which our land-based explorer fails – if you can get through in a boat, there must be an unbroken line running along the river between the two banks, which means the land-lubber won’t be able to find a way across. So there are two situations here, each of which has a probability that can be calculated in the exact same way, and which are mutually exclusive – one succeeds exactly when the other fails.

So it’s much less of a surprise now that each of these scenarios is successful with probability ½ – they’re the answer to effectively the same question, and they can’t both succeed at once, so they must each happen half the time. Someone who shrewdly spotted this correspondence straight away might use this as a way to prove that the probability is ½, without even having to calculate it.

Two sides of the same coin

This kind of symmetry in probability occurs in other situations too. It’s implicit in the basic assumption that the probability of a fair coin landing heads or tails is 50-50. Neither of ‘heads’ or ‘tails’ is special, as far as the physics of coin tossing is concerned – they are equally likely, so they both end up being 50%.

Similarly, if I asked ‘what’s the probability of getting 5 or more heads out of 9 coin tosses’, you could consider it relative to the probability of getting 5 or more tails – one succeeds exactly when the other fails, and since each instance of heads or tails is equally likely, the probabilities overall are each going to be 50%.

It’s important to note that the requirement isn’t just that the two things are mutually exclusive – for example, it could be considered that if I buy a lottery ticket, there are only two possibilities – I either win or I don’t win – but that very much doesn’t make these things equally likely (sadly for me). I’ve seen this reasoning used before, and it does occasionally warrant a gentle reminder that that’s not quite how these things work.

One nice example of when symmetric probability does apply is in the following problem:

If I deal three cards from the top of a standard deck, what is the probability that the third card is a club?

Many people, faced with this question, would begin working out a series of probabilities – what the first and second cards could be, and if the first two cards are or aren’t clubs, how that affects the options for the third card. Tree diagrams might be employed, and numbers on the top and bottom of fractions would go up or down by one. But wait! This situation can be thought of much more simply if you step back and look at it symmetrically.

I could ask the exact same question but change one of the words – for example, clubs could equally be hearts, spades or diamonds. I could also ask about the first card, or the eighteenth, or the last card.

But in a shuffled deck, each card has an equal probability of being in any of the 52 places, and all clubs are equivalent for the purposes of the puzzle. This means that the chances of the third card being a club, however you choose to work it out, will still be ¼ – since if I’d said hearts, spades or diamonds instead, you could calculate it in exactly the same way, and each of these four options occurs exactly when the others don’t.

Symmetry is a powerful and elegant concept in mathematics, and it’s nice to see it pop up in other areas, like probability. Understanding a situation in this way – being able to step back and see the whole thing – might save you hacking through a forest of calculations, when you could climb above and see the way onward much more easily.

Avatar photo

Posted by

is a mathematician based in Manchester, who gives talks and workshops on different areas of maths. She finished her PhD in 2011, and since then has talked about maths in schools, at science festivals, on BBC radio, at music festivals, as part of theatre shows and on the internet. Katie writes blog posts and editorials for The Aperiodical, a semi-regular maths news site.

Leave a Reply

E-Mail-Benachrichtigung bei weiteren Kommentaren.
-- Auch möglich: Abo ohne Kommentar. +