[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]

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.

Complete trust in my reliability? Shame on you! Take nobody's word for it!!!

[Guest]

Complete trust in my reliability? Shame on you! Take nobody's word for it!!!

You know it's a booby trap - He's a clever man that DP

[Guest]

You know it's a booby trap - He's a clever man that DP

Think he was trying to trick me into recognising the value of faith? That would be cunning...

[Guest]

They would only have a 50% chance of finding another way to the island. Unless all the bridges explode.

[itachi-san]

I strongly disagree with 50% and the coin flip analogy. With this problem the tank needs to get across multiple bridges (at least 3) to get across.Therefore, you have to take all previously crossed bridges' probabilities into account. The shortest number of bridges the tank can cross is 3, but that doesn't mean it will cross 3. I'm not sure what the math would be to determine the number of bridges crossed, but the answer is at the most 1/2 * 1/2 * 1/2 = .125, though I'm certain the answer is lower because the amount of bridges to be crossed is higher than 3 since the original question doesn't ask for the least amount. Can anyone help on the math for that? (is it really 7-3=4? and if so, why?)

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

50%

[Guest]

50%

[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%

like many i was thinking into the 50% trap but you've explained it more clearly then the rest and therefore came up with an outcome of a 1-in-8 chance, i must agree with you there

[Guest]

100%

[Guest]

sorry, but i cant agree with 50%

i would put like 100 detonators hooked to a huge pile of explosives under each bridge

when the tanks got to islands, i would blow it all up

im going to assume that at least 1 of the 100 detonators on each pile would work

then i would start taking pot shots at the tanks trapped on the islands

i'd give 'em a .01% chance

no one said we only got 13 detonators or explosives

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

Well, the best thing I can think of is

3/8 because to stop them you need to blow up all three bridges laterally. There is a 1/2 chance of each bridge blowing up, and there are three bridges laterally- 1/2 cubed is 1/8, and there are three lateral paths, therefore it is 3/8.

[Guest]

That doesn't cover the full range of possibilities. For example you could stop the tanks by blowing up a diagonal line of 5 bridges. There's an easier way to solve this.

The puzzle has a kind of symmetry which is not immediately obvious

[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?

I'm afraid I'm new to this forum and these kinds of things ... but I do know a math puzzle when I see one ... I'm sending this to a friend who knows his math, and he ought to be able to give us a firm number.

Now of course if it's got one of those easy, clever, and post-obvious answers, so be it ... but I still think it can be solved mathematically.

Edited December 4, 2008 by zanthal

[Yoruichi-san]

Thanks to the ppl who dug this up...

I see what Octopuppy is saying about 'a kind of symmetry that is not immediately obvious'...I think he's using the term 'symmetry' in the mathematical sense (i.e. like an transformation/operator that returns the equivalent configuration), as opposed to the common sense...

Anyways...here is the way I see the 'symmetry'...

Taking each bridge as a possible 'path segment' individually, the tank must move along the path segment, and can only move if the path segment is there. The theoretical boat must move along the water, and can only move if the path segment is destroyed and hence not there blocking it, which I think of as it moving along the 'negative' path segment. The tank is crossing up/down and the boat is crossing left/right, i.e. its crossing is at 90 degrees from the tank.

The tank is trying to cross a grid with 3 columns of 2 path segments parallel to its crossing (up/down), and 2 rows of path segments perpendicular to its crossing (left/right). Turning the picture 90 degrees, I see that the boat is trying to cross a grid with 3 columns of negative path segments (draw X's through the bridges if that helps visualize...each X is a negative path segment) parallel to its crossing and 2 rows of of negative path segments perpendicular to it's crossing. Since each bridge has a 50/50 chance of being a path segment or a negative path segment, the tank and the boat are in equivalent (congruent) situations, hence having the same probability of being able to cross.

Edited December 4, 2008 by Yoruichi-san

[Yoruichi-san]

Ooh...just figured out a better way to illustrate the symmetry simply...

O O O
O O
O O O
O O
O O O

Each circle represents a bridge, which has a 50% chance of either being filled/in place (allowing the tank to pass) or empty/destroyed (allowing the boat to pass). As depicted, the situation is symmetric for vertical and horizontal movement.

[Guest]

EXTRA PROBLEM

There is an interesting lemma which I've taken for granted here, but it's perhaps worthy of more consideration.

DON'T LOOK UNTIL YOU'VE ANSWERED THE MAIN PUZZLE ! ']This refers to the

solution I posted earlier, where P_B and P_T are probabilities of boat getting though (event B) and tank getting across (event T)

The answer (P_T=0.5) relies on two statements;

1) Events B and T are mutually exclusive and the only possible results: P_B+P_T=1

2) Events B and T have the same probability since the boat and tank have the same shaped grid layouts with 50% probability at every point: P_B=P_T

The second of those statements is the one which is not obvious, and tends to confuse people.

But perhaps we've taken the first statement for granted a little. Sure, B and T are mutually exclusive, since any route the tank could take forms a continuous line which the boat cannot cross, and vice versa.

But what about other possible outcomes?

How do we know that there is not some possible combination of bridge collapses which would leave both the tank and boat unable to pass?

I don't think there is, but can anybody prove it?

EDIT: Please don't mention the boat outside of a spoiler!

[Guest]

Very simple--take either the first row or bridges or the last and blow them up. This prevents the tanks from advancing. The other row of bridges would prevent the boats from advancing.

Also, on the main puzzle--in theory, the boat idea is flawed because blowing up any of the exterior bridges running parallel with the boat (cross-stream) that the boat was next to would allow the boat to pass outside the bridge area and move unhindered to the other side.

[Guest]

Also, there would be combinations that would allow both the boat and tank to pass through. If one side (the boat's startpoint) was completely blown away, but the other side (the truck's startpoint) was completely left standing, boats and trucks could both reach the other side.

[Guest]

I think you're misunderstanding what was meant there, but since it kind of gives the game away with the main puzzle we should use spoilers...

...while the tanks want to get from one side of the river to the other, the boat wants to get from one end of the river to the other (the boat has essentially the same problem turned through 90^o). This insight into the puzzle is what unlocks it, so I'd rather you didn't mention boats outside of a spoiler! So for example if (as in your 1st answer) you blew up the 1st row of bridges, that stops the tanks and simultaneously creates a channel which allows the boat to go through. But leave one standing to block the boat, and you've created a way for the tanks to cross. But since there's 13 bridges, there's 2¹³ possible outcomes, so can we be sure there is no way to block both? I hope that makes it clearer!

[Guest]

50 percent

[Guest]

Ok--definitely misunderstood what was meant by the boats and boats and tanks...and apologies for the lack of spoilers--the further the replies get from the OP, the more often I forget to use them

[Guest]

Adding the boats to the equation just makes it simpler to illustrate the 50/50 situation. It works with or without the boats.

Every bridge that gets blown up essentially creates a "bridge" for a boat. To prevent a tank from crossing, you MUST create path that the boats could navigate across.

Therefore, the probability that a tank can still cross, with any given explosion outcome, will be exactly the opposite that the boat will be able to cross with that same outcome.

If you add together the resulting probabilities on the tank side, and the resulting opposite probabilities on the boat side, regardless of how many total probabilities there are, the totals must ultimately equal each other.

Since there are two outcomes available: either 1)the tank passes or 2)the tank does not pass (the opposite being true for the boat, of course), this means the boat and tank have to end up with the same overall probability of crossing/not crossing.

To sum up:

1) Probability that tank crosses = probability that boat does not cross

2) Probability that tank does not cross = probability that boat does cross

3) therefore, probability that tank crosses = probability that boat crosses

4) 100% probability divided between 2 established outcomes = 50%

and... (I haven't done this since High School...)

5) QED?

[Guest]

Adding the boats to the equation just makes it simpler to illustrate the 50/50 situation. It works with or without the boats.

Every bridge that gets blown up essentially creates a "bridge" for a boat. To prevent a tank from crossing, you MUST create path that the boats could navigate across.

Therefore, the probability that a tank can still cross, with any given explosion outcome, will be exactly the opposite that the boat will be able to cross with that same outcome.

If you add together the resulting probabilities on the tank side, and the resulting opposite probabilities on the boat side, regardless of how many total probabilities there are, the totals must ultimately equal each other.

Since there are two outcomes available: either 1)the tank passes or 2)the tank does not pass (the opposite being true for the boat, of course), this means the boat and tank have to end up with the same overall probability of crossing/not crossing.

To sum up:

1) Probability that tank crosses = probability that boat does not cross

2) Probability that tank does not cross = probability that boat does cross

3) therefore, probability that tank crosses = probability that boat crosses

4) 100% probability divided between 2 established outcomes = 50%

and... (I haven't done this since High School...)

5) QED?

Every bridge that gets blown up essentially creates a "bridge" for a boat. To prevent a tank from crossing, you MUST create path that the boats could navigate across.

That's what I'm asking for proof of at the moment. Obviously that holds for a single bridge, but how can we be sure there is no overall combination which prevents both tank and boat from crossing?

To sum up:

1) Probability that tank crosses = probability that boat does not cross

2) Probability that tank does not cross = probability that boat does cross

3) therefore, probability that tank crosses = probability that boat crosses

(3) is not implied by anything you mentioned. (1) and (2) only tell us that these probabilities add up to 1.

[Guest]

Every bridge that gets blown up essentially creates a "bridge" for a boat. To prevent a tank from crossing, you MUST create path that the boats could navigate across.

That's what I'm asking for proof of at the moment. Obviously that holds for a single bridge, but how can we be sure there is no overall combination which prevents both tank and boat from crossing?

To sum up:

1) Probability that tank crosses = probability that boat does not cross

2) Probability that tank does not cross = probability that boat does cross

3) therefore, probability that tank crosses = probability that boat crosses

(3) is not implied by anything you mentioned. (1) and (2) only tell us that these probabilities add up to 1.

Darn! All that internal gloating for nothing! Lets try again:

you have to eliminate any combination of bridges that leave one side connected to the other.

Using Y-sans diagram, where the small circles represent bridges. We need to add an "x" in the spaces between the circles where the islands should be. We can fill in a circle to represent an exploded bomb, creating a dot.

Now, go ahead and blow up any amount of bombs you like and fill in the dots.

The next step is the fun one. Connect the dots LA LA LA! Connect any filled in dots that are adjacent, but do not have an island between them. This represents open water that a tank cannot cross, but a boat can. If this line connects one of the three spots on the left to one of the three on the right, the tanks are stopped, but the boat can go through.

Now, connect any unfilled circle to any horizontally or vertically adjacent "x" to represent the path a tank can go but a boat cannot. Again, if a line is formed that connects circles completely from top to bottom, the tank may cross and the boats are denied.

The only way both tank and boat can be stopped from crossing is if both of the above lines are formed and DO NOT CROSS. This, of course, cannot happen.

Keep in mind, while picking this one apart, that I don't write proofs often. That, and I'm up WAY past my bedtime here!

Edited December 5, 2008 by Grayven

[Guest]

I'm not sure if that's 100% there, though I think I see what you're driving at. Having mulled it over a few hours, here's my attempt at it:

Here's a diagram of one possible layout. Land and water areas are green and blue respectively and bridges (the squares) are considered land or water areas depending on whether or not they blew up.

Starting at point A, we can trace along the "shoreline" with the water always on the right. Note that:

1) There are only a finite number of line segments we can use, and

2) There is no way the line can double back or loop, therefore each line segment can be used only once

This guarantees that the line must hit a dead end at some point. But there are only 4 possible dead ends, at points A,B,C and D. The line cannot reach D because (going from A) the line always keeps the water on the right, and to approach D you would have to have it on the left. It cannot return to A for the same reason, and also because there is no way to turn back.

So it must reach B or C. In the diagram example it will go to C. In this case a tank can cross the river by following the line, keeping it on the right. If the line reaches B, a boat can pass through, keeping the line on its left. There are no other possibilities.

As a kid I was always fascinated by the board layout on the game show Blockbusters. It was very well designed because one team could always connect a line and there was no way to reach a stalemate. The same principle applies. It works because the hexagonal layout means that every node is a 3-node, just like in the bridge problem.