A computer science problem by Bill Tomlinson

As shown in the image, there is a river running between 2 banks. There are 9 islands in the river, and these land masses are connected by 18 bridges. The inhabitants can only use these bridges to get across the river (no swimming, boats, etc. are allowed).

One day, an extremely heavy storm destroys at least one of the bridges, which prevents the inhabitants from crossing directly between the connected land masses. Out of the \( 2^{18} - 1 = 262143 \) cases where at least one bridge is destroyed, in how many cases can the inhabitants still cross between the two banks?

\(\)
Hint: The trick used to solve the previous problem cannot be used here. Good luck!

×

Problem Loading...

Note Loading...

Set Loading...