[Guest]

Every now and then you see a puzzle, peek at the answer, then wish you'd taken the time to solve it instead of peeking. I did that with this puzzle, but I won't post the solution now so you don't make the same mistake. Enjoy!

A river has six islands in the middle, connected by 13 bridges as shown:

Enemy tanks are approaching on the other side of the river, so you've set up explosives to blow up the bridges. Unfortunately your detonators came from a dodgy batch, so each bridge has only a 50% chance of blowing up (independently of the others). What is the probability that the enemy tanks will still be able to find a route across the river?

If you find yourself doing any complicated calculations, you're barking up the wrong tree! Try a little lateral thinking instead...

EDIT: When you've solved this, there's a related, more general question to consider here...

[Guest]

Is it 50%? If each bridge has a 50% chance of blowing up? Not sure if it's right, but you said think laterally

[Guest]

Is it 50%? If each bridge has a 50% chance of blowing up? Not sure if it's right, but you said think laterally

No guessing! It's how you work it out that matters...

[Guest]

Every now and then you see a puzzle, peek at the answer, then wish you'd taken the time to solve it instead of peeking. I did that with this puzzle, but I won't post the solution now so you don't make the same mistake. Enjoy!

A river has six islands in the middle, connected by 13 bridges as shown:

Enemy tanks are approaching on the other side of the river, so you've set up explosives to blow up the bridges. Unfortunately your detonators came from a dodgy batch, so each bridge has only a 50% chance of blowing up (independently of the others). What is the probability that the enemy tanks will still be able to find a route across the river?

If you find yourself doing any complicated calculations, you're barking up the wrong tree! Try a little lateral thinking instead...

The probability of being able to cross the bridges is the same as the probability that you won't be able to sail your boat past these bridges. Think about it. If there is a path across the river, there is no way there is a path past the bridges along the river. If there is a path past the bridges along the river, then there is no way you can cross the bridges. This means these two probabilities must be mutually exclusive.

These two cases are equal because either way, you're trying to cross a 3x3 grid.

Since there is no other case and these two cases are equal and must add up to 100%, each has a 50% chance of being true. Therefore, there is a 50% chance the tanks can cross.

[Guest]

No guessing! It's how you work it out that matters...

Who said anything about a guess?

[Guest]

The probability of being able to cross the bridges is the same as the probability that you won't be able to sail your boat past these bridges. Think about it. If there is a path across the river, there is no way there is a path past the bridges along the river. If there is a path past the bridges along the river, then there is no way you can cross the bridges. This means these two probabilities must be mutually exclusive.

These two cases are equal because either way, you're trying to cross a 3x3 grid.

Since there is no other case and these two cases are equal and must add up to 100%, each has a 50% chance of being true. Therefore, there is a 50% chance the tanks can cross.

I think you got something wrong. It sounds like you're saying there's a chance that a die might land with 5 up, and an equal chance that it won't land with any other number up, so they must equal 100% so it must be 50% that the die will land with a 5 up.

EDIT--

Wait, i think i just understand what you were trying to say. You're wording is a little confusing, but i do see what you're saying.

But i still think your reasoning is faulty

Edited March 18, 2008 by Noct

[Guest]

i would say

the tank has to cross at least 3 bridges and each has 50% chance of blowing so

50% X 50% = 25%

25% X 50% = 12.5%

[Guest]

i would say

the tank has to cross at least 3 bridges and each has 50% chance of blowing so

50% X 50% = 25%

25% X 50% = 12.5%

But that would be the chance of just three bridges across. We also have to add in the probabilities of 4+ bridges (i believe)

[Guest]

The probability of being able to cross the bridges is the same as the probability that you won't be able to sail your boat past these bridges. Think about it. If there is a path across the river, there is no way there is a path past the bridges along the river. If there is a path past the bridges along the river, then there is no way you can cross the bridges. This means these two probabilities must be mutually exclusive.

These two cases are equal because either way, you're trying to cross a 3x3 grid.

Since there is no other case and these two cases are equal and must add up to 100%, each has a 50% chance of being true. Therefore, there is a 50% chance the tanks can cross.

Bravo, I am very very impressed

[Guest]

Every now and then you see a puzzle, peek at the answer, then wish you'd taken the time to solve it instead of peeking. I did that with this puzzle, but I won't post the solution now so you don't make the same mistake. Enjoy!

A river has six islands in the middle, connected by 13 bridges as shown:

Enemy tanks are approaching on the other side of the river, so you've set up explosives to blow up the bridges. Unfortunately your detonators came from a dodgy batch, so each bridge has only a 50% chance of blowing up (independently of the others). What is the probability that the enemy tanks will still be able to find a route across the river?

If you find yourself doing any complicated calculations, you're barking up the wrong tree! Try a little lateral thinking instead...

I would say-by lateral thinking- that the probability would be 1, as they would find another way across the river if the bridges were gone. The problem is not a route on these bridges across the river.

probability would be more difficult, as the probability that they can go straight across, 3 bridges, is 3*.125 or .375, as there are 3 independent ways to do that (P(a or b or c)) Then you have to add in the other routes-4 bridges, 5 bridges, 6 bridges, and 7 bridges. Here you have to take into account that they cannot use another-shorter-route, so with the 7 bridges, the only way is if you blow up the other 6, and there are 2 possible routes, so the probability they have to use all 7 bridges is .000244. The rest would become complicated, which we want to avoid. Therefore, I would guess at this point that the probability is near .5 that they can cross, still using the bridges.

Of course, the probability that they cannot cross because a series of 3 is destroyes is also .375. (.125 for any of the 3 sets of 3).

Edited March 18, 2008 by statman

[Guest]

The probability of being able to cross the bridges is the same as the probability that you won't be able to sail your boat past these bridges. Think about it. If there is a path across the river, there is no way there is a path past the bridges along the river. If there is a path past the bridges along the river, then there is no way you can cross the bridges. This means these two probabilities must be mutually exclusive.

These two cases are equal because either way, you're trying to cross a 3x3 grid.

Since there is no other case and these two cases are equal and must add up to 100%, each has a 50% chance of being true. Therefore, there is a 50% chance the tanks can cross.

I agree with Noct that this reasoning isn't quite valid. Your statement that the two cases are equal because either way you're trying to cross a 3x3 grid is incorrect. If you look at the diagram it is actually a 2x3 grid, with bridges forming the sides of length 3 (which can be destroyed), whereas land forms the sides of length 2 (which can't). This means that it isn't an identical problem going from left to right as from top to bottom.

For example, if it was a 1x1 grid, we would have two bridges going from top to bottom only, with land forming the top and bottom. Here, for the tanks to get across they would only need one bridge to remain standing, whereas for a boat to get through it would need both bridges to be destroyed, so the likelihood of the tanks getting across is greater than 50% (75% in this case).

Whilst I'm not saying you are wrong with your answer of 50%, I am saying that the reasoning makes an assumption that isn't as obvious one to make as you may think, so needs proof in itself.

[Guest]

well, seeming as how the hardest and longest way to get acrossed is 7 bridges whole, and the shortest is 3 bridges whole, 7-3=4 so .5/2/2/2= 1/16 or 6.25 % chance.....

kiger

[Guest]

Geeeeez - I have to put up a general disagreement to 50% (because I can't come up with a solid answer myself, just reasoning why it's greater than 50%)

For the tanks to be prevented from crossing, three parallel bridges need to be destroyed (connecting to near shore, in between islands, or connecting to far shore). If we assume random blowing up, then knock out one each of those (so we're left with four more successful explosions, which may be a stretch since only 50% work, but we'll give the bomb makers the benefit of the doubt today ). Perpendicular to those, let's take out two of those four. Now we have two explosions left. Soooooooo what's the probability of taking out two bridges next to each other out of the six possible bridges left?? I don't know, because I'm getting old and can't remember math, but I do know it's significantly less than 50%. I'm going to feel like such a dork when the answer to this is posted, though

[Guest]

50%

In case you're wondering why ...

DEFINITIVE ANSWER: 50%

Quick Reasoning: There is no one "magic bridge" or even two "magic bridges" or even three ... that can prevent crossing. Just because you knock out one legit path, there may still be another. In reality, there are 29 legit paths across, and in net effect, there is either a way or there isn't. Think of it as a puzzle of heads and tails ... it's like the probability of all heads vs. all tails - doesn't matter which comes up in between, there is still, in net result, one way to do each. Thus 50%.

And if you must test ... (like I did)

29 valid paths, spanning 13 possible bridges. Total # combinations of results = 2^13 = 8192

Total # results that include at least one possible path = 4096. (I wrote a quick computer program to count and test.)

[Guest]

For those that wanted to see the code ...

Assume the following for the island setup:

' START

A B C

x 1 x 2 x

D E F

x 3 x 4 x

G H I

' FINISH

where A,B,C...I,1,2,3,4 all represent bridges (paths)

Public Class Form1

    Private Sub btnAction_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnAction.Click

        Dim numCombos As Integer = 0

        Dim numPaths As Integer = 0

        For pathA As Integer = 0 To 1

            For pathB As Integer = 0 To 1

                For pathC As Integer = 0 To 1

                    For pathD As Integer = 0 To 1

                        For pathE As Integer = 0 To 1

                            For pathF As Integer = 0 To 1

                                For pathG As Integer = 0 To 1

                                    For pathH As Integer = 0 To 1

                                        For pathI As Integer = 0 To 1

                                            For path1 As Integer = 0 To 1

                                                For path2 As Integer = 0 To 1

                                                    For path3 As Integer = 0 To 1

                                                        For path4 As Integer = 0 To 1

                                                            numCombos = numCombos + 1

                                                            If ValidPath(pathA, pathB, pathC, pathD, pathE, pathF, pathG, pathH, pathI, path1, path2, path3, path4) Then

                                                                numPaths = numPaths + 1

                                                            End If

                                                        Next

                                                    Next

                                                Next

                                            Next

                                        Next

                                    Next

                                Next

                            Next

                        Next

                    Next

                Next

            Next

        Next


        UpdateControls(numCombos, numPaths)

    End Sub


    Private Sub UpdateControls(ByVal numCombos As Integer, ByVal numPaths As Integer)

        txtCombos.Text = numCombos

        txtPaths.Text = numPaths

    End Sub


    Private Function ValidPath(ByVal pathA As Boolean, ByVal pathB As Boolean, ByVal pathC As Boolean, ByVal pathD As Boolean, ByVal pathE As Boolean, ByVal pathF As Boolean, ByVal pathG As Boolean, ByVal pathH As Boolean, ByVal pathI As Boolean, ByVal path1 As Boolean, ByVal path2 As Boolean, ByVal path3 As Boolean, ByVal path4 As Boolean) As Boolean

        'possible paths		

        'adg	    b1dg	cfi

        'ad3h	    b1d3h	cf4h

        'ad34i	    b1d34i	cf43g

        'ad3e2fi	be3g	cf4e1dg

        'a1eh	    beh	    c2eh

        'a1e3g	    be4i	c2e3g

        'a1e4i	    b2fi	c2e4i

        'a12fi	    b2f4h	c21dg

        'a12f4h	    b2f43g	c21d3h

        'a12f43g            c21d34i

        If pathA Then

            If pathD Then

                If pathG Then

                    Return True

                End If

                If path3 Then

                    If pathH Or (path4 And pathI) Or (pathE And path2 And pathF And pathI) Then

                        Return True

                    End If

                End If

            End If

            If path1 Then

                If pathE Then

                    If pathH Or (path3 And pathG) Or (path4 And pathI) Then

                        Return True

                    End If

                End If

                If path2 And pathF Then

                    If pathI Or (path4 And pathH) Or (path4 And path3 And pathG) Then

                        Return True

                    End If

                End If

            End If

        End If

        'b1dg

        'b1d3h

        'b1d34i

        'be3g

        'beh

        'be4i

        'b2fi

        'b2f4h

        'b2f43g

        If pathB Then

            If path1 And pathD Then

                If pathG Or (path3 And pathH) Or (path3 And path4 And pathI) Then

                    Return True

                End If

            End If

            If pathE Then

                If (path3 And pathG) Or pathH Or (path4 And pathI) Then

                    Return True

                End If

            End If

            If path2 And pathF Then

                If pathI Or (path4 And pathH) Or (path4 And path3 And pathG) Then

                    Return True

                End If

            End If

        End If

        'cfi

        'cf4h

        'cf43g

        'cf4e1dg

        'c2eh

        'c2e3g

        'c2e4i

        'c21dg

        'c21d3h

        'c21d34i

        If pathC Then

            If pathF Then

                If pathI Then

                    Return True

                End If

                If path4 Then

                    If pathH Or (path3 And pathG) Or (pathE And path1 And pathD And pathG) Then

                        Return True

                    End If

                End If

            End If

            If path2 Then

                If pathE Then

                    If pathH Or (path3 And pathG) Or (path4 And pathI) Then

                        Return True

                    End If

                End If

                If path1 And pathD Then

                    If pathG Or (path3 And pathH) Or (path3 And path4 And pathI) Then

                        Return True

                    End If

                End If

            End If

        End If


        'not in paths

        Return False

    End Function

End Class

[/codebox]

[Guest]

That's a quick computer program?!

[Guest]

Nice to see that's got a few people thinking!

Seventh Sage is right on the button, here's the complete spoiler for anyone who's having difficulty seeing the logic in that:

A tall boat which wants to sail from one end of the river to the other can sail under any bridge which has been destroyed. In effect the boat is looking at 13 potential channels it can sail through, connecting 6 pools of water (see red bits on diagram)

I hope that makes the symmetry a little clearer.

Each channel has a 50% chance of being open, so if 'B' is the boat getting through, and 'T' is the tank getting through:

P_B=P_T

Also, these events are mutually exclusive and there is no other possibility, so:

P_B+P_T=1

so

P_T=0.5

[Guest]

I say call the engineers/sappers build a pontoon and hope that there is no enemy within - espionage!

Blown away yet?

[Guest]

Maybe i'm too a military minded but if i knew i had 13 bobms that each had a 50% chance to blow up i would place one on each bridge.... I'd place 4 on the each of the first set of three across (and the extra u say? well throw it in the river maybe you can blow up some fish for dinner, he 50% ull get something right? better than burger king in some cases lol). Thus giving a better chance to destroy the bridges and reducing the chance the enemy tanks would cross.

[Guest]

i think it is less then 50% because each bridge has a 50% chance of blowing up but a 100% chance of becoming weaker with the wieght of the tanks ontop of the bridges they could collapse with the tanks on them.

[Guest]

Nice to see that's got a few people thinking!

Seventh Sage is right on the button, here's the complete spoiler for anyone who's having difficulty seeing the logic in that:

A tall boat which wants to sail from one end of the river to the other can sail under any bridge which has been destroyed. In effect the boat is looking at 13 potential channels it can sail through, connecting 6 pools of water (see red bits on diagram)

I hope that makes the symmetry a little clearer.

Each channel has a 50% chance of being open, so if 'B' is the boat getting through, and 'T' is the tank getting through:

P_B=P_T

Also, these events are mutually exclusive and there is no other possibility, so:

P_B+P_T=1

so

P_T=0.5

Sorry, but I still don't think that this spoiler stands up to scrutiny. In your proof you make an assumption that two probabilities are equal, mutually exclusive and 50% and the subsequent equations are just rearranged to return to your original assumption. Your assumption is a valid one, as you are talking about an individual channel, but at no point do you make a valid argument why this should then apply to the overall solution.

If we look at the following variation (excuse the bad diagram!):

------

| | |

0-0-0

| | |

------

then your reasoning would still apply. I.e. there are 8 bridges and a boat would have 8 potential channels connecting 4 pools of water. Each channel has a 50% chance of being open (... do same equations ...) so the probability of tanks getting across is 0.5. But in this case it's not - it's actually about 0.67!

Also, someone has mentioned something about "magic bridges", where no one bridge can completely stop the tanks or boats from getting through. This problem also contains no magic bridges, but still isn't a probability of 50%.

I'm not disputing the answer, especially as someone has now proven it by brute force, but I don't think anyone has given a concrete argument for why this is the answer.

Out of interest, the following problem has the same solution as the original one:

----

| |

0-0

| |

----

Does it follow that all problems consisting of a grid of dimensions n x (n+1) have the same solution??

[Guest]

my first way shows 0% propability by using using a mobile phone rigged to small gunpowder charge embedded in a TNT stick placed nicely atop the crates of high explosive needed to destroy the bridge then without using the dodgey detonators phone it in bang bang bang.

Sceond just use multiple detonators on each of the bridges . the probability of the enemy getting across would halve at each brige for each detonator

[Guest]

I would just wait for the tanks to get halfway and then detonate them.

boom...

Edited March 19, 2008 by Kitty in the sky

[Guest]

I agree with Neida. That's what I was trying to say earlier. Your argument is faulty. You may have the right answer. But your explanation only applies to each individual bridge singly. You haven't provided an explanation for the whole problem.

[Guest]

Sorry, but I still don't think that this spoiler stands up to scrutiny. In your proof you make an assumption that two probabilities are equal, mutually exclusive and 50% and the subsequent equations are just rearranged to return to your original assumption. Your assumption is a valid one, as you are talking about an individual channel, but at no point do you make a valid argument why this should then apply to the overall solution.

If we look at the following variation (excuse the bad diagram!):

------

| | |

0-0-0

| | |

------

then your reasoning would still apply. I.e. there are 8 bridges and a boat would have 8 potential channels connecting 4 pools of water. Each channel has a 50% chance of being open (... do same equations ...) so the probability of tanks getting across is 0.5. But in this case it's not - it's actually about 0.67!

My reasoning depends on the layout of the bridges (here I think scuttill may have got it wrong). Different layouts (1x3 islands, 2x2 islands and so on) will give different probabilities...

Out of interest, the following problem has the same solution as the original one:

----

| |

0-0

| |

----

Does it follow that all problems consisting of a grid of dimensions n x (n+1) have the same solution??

Yes! That's the point! When you have a grid of n x (n+1) islands (connected by bridges), you will also get a corresponding grid of (n+1) x n pools (connected by channels) from the boat's point of view. The boat's probability is the same as the tank's probability because of this - it has an analogous grid of the same dimensions, where the probabilities are all the same, only mutually exclusive. Look at the diagram in my spoiler, then turn your head to look at it on its side. The boat is facing the same problem as the tank. Same layout. Same probability.

In your earlier counterexample (1 x 3 islands) the boat's grid would consist of 2 x 2 pools. The boat's grid has a different layout to the tank's grid so it could have a different probability, and it does!

[Guest]

I always like puzzles that have a simple proof which is either counter-intuitive or hard to grok, but which, after you look at it long enough, results in a large and satisfying *click* in the middle of your skull. This was one of those problems. I really wanted to argue the flaw in your logic, but the brute force solution that had already been presented, combined with my complete trust in your reliability, prevented me from jumping in. And now I get it.

I'm hoping that if I keep working at problems that I seem unable to solve, it will somehow make me smarter. So far it doesn't seem to be working.