[Breaking News] Storm sweeping through a river!

Above diagram is a reconstruct of the original problem.

Assume a ship is going through the bridges. From one blue side to another.

But the bridges are too low for the ship to go through, so the ship can only go through the broken ones.

Now you'll notice that the yellow paths look like the same as the black ones. Only $90^{\circ}$ rotated.

If people can cross the bridges, then the ship won't be able to cross. If people can't, the ship can. (Do you see why?)

---

Now we will try to create a bijection between people crossing and ships crossing.

Toggle all the yellow-paths, and then rotate it by $90^{\circ}$ counterclockwise.

Then let's call it the counterpart of the bridge-path.

For every bridge-path that doesn't allow people to cross from one side to another, there is a counterpart that allows them, except for the case where every bridge is destroyed -- which means one case that doesn't allow people to cross is left out with no counterpart.

Therefore, the number of cases where people can't cross is $1$ greater than the number of cases where people can.

There are total of $2^{13}-1$ cases, and if we say that the number of cases where people can cross from one side to another is $a$ ,

$a+(a+1)=2^{13}-1$

Therefore $a=2^{12}-1=\boxed{4095}$ .

Lets try to generalise this question.

As we can clearly see there are

No. of Islands = N x (N+1)

No. of bridges = N^2 +(N+1)^2

here N = 2, but it will be hard to calculate for this so will try starting from N = 0,1

Case 1:

N = 0,

No. of islands = 0 x 1 = 0

No. of Bridges = 0^2 + 1^2 = 1

Possible Combinations = 2^1 = 2 [ where 2 = No. of banks and powered by no. of bridges i.e., 1 in this case]

After storm there will be 50% chance that inhabitant can cross the banks i.e, 1 in this case

But according to question at least 1 bridge should be destroyed, in this there is only 1 bridge.

Hence 0 cases to cross the banks.

Case 2:

N = 1

No. of islands = 1 x 2 = 2

No. of Bridges = 1^2 + 2^2 = 5

Possible Combinations = 2^5 = 32

[Explanation of 32 possible combinations:

1. When 0 of 5 bridges are damaged = $_{0}C^{5}$ = 1

2. When 1 of 5 bridges are damaged = $_{1}C^{5}$ = 5

3. When 2 of 5 bridges are damaged = $_{2}C^{5}$ = 10

4. When 3 of 5 bridges are damaged = $_{3}C^{5}$ = 10

5. When 4 of 5 bridges are damaged = $_{4}C^{5}$ = 5

6. When 5 of 5 bridges are damaged = $_{5}C^{5}$ = 1

Total = 32, 1st is the combination where no bridge is destroyed ]

After storm there will be 50% chance that inhabitant can cross the banks i.e, 16 in this case

But according to question at least 1 bridge should be destroyed, in this there is only 1 case where No bridge will be damaged

Hence 15 cases to cross the banks.

Case 2:

N = 2

No. of islands = 2 x 3 = 2

No. of Bridges = 2^2 + 3^2 = 13

Possible Combinations = 2^13 = 8192

After storm there will be 50% chance that inhabitant can cross the banks i.e, 4096 in this case

But according to question at least 1 bridge should be destroyed, in this there is only 1 case where No bridge will be damaged

Hence 4095 cases to cross the banks.