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.

As each planet has 3 transporters, there are 30 transporters, providing 15 direct links.  Each link connects with two other links at each end for a total of 4 link pairs that a particular link belongs to, but this counts each link pair twice, so there are 30 link pairs, good for a one-stopover trip.  That makes 45 planetary connections in all--exactly the number of combinations of 10 planets taken two at a time, so we can't allow the same two planets be connected in more than one way.  The following diagram shows direct connections with a *, and one-stopover trips with v (for via) and the planet that makes the connection.

      A   B   C   D   E   F   G   H   I   J
A     -   *   *   *  vB  vB  vC  vC  vD  vD 
B         -  vA  vA   *   *  vE  vF  vE  vF 
C             -  vA  vG  vH   *   *  vH  vG
D                 -  vI  vJ  vJ  vI   *   *
E                     -  vB   *  vI   *  vG
F                         -  vJ   *  vH   *
G                             -  vC  vE   *
H                                 -   *  vF
I                                     -  vD
J                                         -

Method was:

First fill in connection of A to B, C and D.

Then, for each L-shaped column/row, for B, C, etc. in turn, going down the column and across the row, add a * only when the two planets were not already either directly connected or connected via another planet and no new indirect connection would be formed that duplicates a previous direct or indirect connection.  That's because, as mentioned above, no connections can be wasted--there are only 45 to go around. Of course stop assigning *'s when a given planet has 3, and go on to consider the next planet.  Keep track of the via connections so that you don't over-connect any pair of planets. At the end, you'll have the above table.

Note for example that when doing planet C, when you get to the column for planet E, you cannot place a direct connection there, as that would create an indirect connection between B and C via E, even though an indirect connection via A already existed, so that intersection had to be skipped, to await a subsequent indirect connection.

Edited on November 16, 2005, 10:23 am

Posted by Charlie on 2005-11-16 10:21:05