A computer science problem by Bill Tomlinson

The matrix A stores the number of bridges between each pair of locations. From the starting bank, pick a bridge to any of the islands.

Case 1: That bridge is destroyed, then just delete that bridge from A, and compute f.

Case 2: That bridge is not destroyed, then that island may as well be on the bank, so I imagine moving that island to the bank, (along with any bridges coming off that island). Then compute f.

Then we add the 2 results together and repeat this process. This ends when the starting bank is not connected to any islands. Then if a is the number of bridges between the 2 banks, there are $2^{a}-1$ subsets of those bridges which could be destroyed, and if b is the number of other bridges, there are $2^{b}$ subsets of those which could be destroyed. So the number of subsets of bridges which could be destroyed is $2^{b}(2^{a}-1)$

Here's my MATLAB code. The matrix A stores the number of bridges between locations. The first and last rows/columns correspond to the starting and ending banks.

function [output]=f(A)
    n=size(A,1);

    for j=2:n-1
        if A(1,j)
            x=A(1,j);
            A(1,j)=0; A(j,1)=0;
            output=f(A);
            A(1,:)=A(1,:)+A(j,:);
            A(j,:)=[];
            A(:,1)=A(:,1)+A(:,j);
            A(:,j)=[];
            output=output+f(A)*(2^x-1);
            return
        end
    end

    E=sum(sum(A))/2;
    output=2^(E-A(1,n))*(2^A(1,n)-1);
end

We have to remember to subtract 1 at the end since we don't want to count the case where no bridges are destroyed.

To set up A I used the code below, but there are only 18 edges, so you could just add them one at a time.

A=zeros(11);
for i=1:3
    A(1,i+1)=1;
    A(i+7,11)=1;
    A(3*i-1,3*i)=1;
    A(3*i,3*i+1)=1;
    A(i+1,i+4)=1;
    A(i+4,i+7)=1;
end
A=A+A';