• 0
Sign in to follow this  
Followers 0

Question

Posted · Report post

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:

post-4017-1205863443_thumbgif

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...

0

Share this post


Link to post
Share on other sites

57 answers to this question

  • 0

Posted · Report post

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

:)
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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...
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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:

post-4017-1205863443_thumbgif

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Who said anything about a guess?

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by Noct
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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%

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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 by statman
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 :)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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]

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

That's a quick computer program?!

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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)

post-4017-1205910598_thumbgif

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:

PB=PT

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

PB+PT=1

so

PT=0.5

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

Blown away yet?

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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: lol). Thus giving a better chance to destroy the bridges and reducing the chance the enemy tanks would cross.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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)

post-4017-1205910598_thumbgif

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:

PB=PT

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

PB+PT=1

so

PT=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??

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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

boom...

Edited by Kitty in the sky
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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!

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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. :D

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. ;)

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.