An alliance of ten planets has decided to build teleporters so that their economies may mutually benefit from faster travel. The teleporters are huge gateways that come in permanently linked pairs. The idea is that each pair of linked teleporters connects a pair of planets.
In the interest of equality, each planet will build exactly three teleporters. In the interest of efficient travel, the links will be placed such that to reach one planet from another, no more than two teleporters must be used. How will the planets be linked?
Bonus: If you were to draw a diagram of the way the planets are linked, what is the simplest diagram you can think of? Try to find one you can even describe in words alone.
Begin with two pentagrams. Each planet in each pentagram is only two hops away from another planet. Now link one planet (A) from one pentagram with a planet (F) from the other. Now each of these planets is two hops away from three planets in the other pentagram. Link the neighbors of one of these planets with the two "currently unreachable in two hops" planets in the other pentagram. Now this planet can reach all the others in two hops. Make the remaining two links in similar fashion.
Two pentagrams (A B C D E) (F G H I J), linked in clockwise order
Then connect A-F, B-I, C-G, D-J, E-H
Edited on November 16, 2005, 9:14 am
solution
