Nine Islands

Probability Level 5

There are nine islands mutually connected by bridges, such that no two bridges intersect. If each island can be visited only once, how many possible ways are there to traverse between any selected pair of islands?

Notes:

1) All islands are interconnected to form a complete network.

2) By 'no two bridges intersect', I mean they to not form 4-way intersections (use your imagination to envision the infrastructural layout).


The answer is 13700.

Steven Zheng by Steven Zheng , 26, China

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Tijmen Veltman
Aug 21, 2014

To travel from one island to another, one can choose to visit any number of islands (from 0 to 7) in any order inbetween. Suppose we visit k k islands before going to the final island, we have a total of 7 ! ( 7 − k ) ! \frac{7!}{(7-k)!} ways to do so: 7 ! 7! if we were to visit every island, over ( 7 − k ) ! (7-k)! for all the islands we don't visit. This gives us a total of:

7 ! 7 ! + 7 ! 6 ! + 7 ! 5 ! + 7 ! 4 ! + 7 ! 3 ! + 7 ! 2 ! + 7 ! 1 ! + 7 ! 0 ! = 13700 . \frac{7!}{7!}+\frac{7!}{6!}+\frac{7!}{5!}+\frac{7!}{4!}+\frac{7!}{3!}+\frac{7!}{2!}+\frac{7!}{1!}+\frac{7!}{0!} = \boxed{13700}.

2 Helpful 0 Interesting 0 Brilliant 0 Confused

I did not derive the formula that way, but your formula is correct. In the end, my derivation is the sum of permutations.

Steven Zheng - 6 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...